[SWEA] D2 - 2001. 파리 퇴치 in 파이썬

문제 출처

SW Expert Academy

 

문제

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.

아래는 N=5 의 예이다.

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.

죽은 파리의 개수를 구하라!

예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.
 

[제약 사항]

1. N 은 5 이상 15 이하이다.

2. M은 2 이상 N 이하이다.

3. 각 영역의 파리 갯수는 30 이하 이다.


[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,

다음 N 줄에 걸쳐 N x N 배열이 주어진다.


[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

---

문제 풀이

부분합을 구하는 문제의 경우 DP 알고리즘을 사용하는 것이 최적화된 방법이지만,

이번 문제는 입력값 N, M이 크지 않기 때문에 그냥 완전 탐색으로 간단하게 구현했다.

 

1. 이중 포문으로 행과 열의 인덱스 값을 순회하면서 동시에 작은 행렬(M*M)의 합을 구한다

2. 작은 행렬의 합을 구하고 max 값과 비교해주면서 다음 인덱스로 이동한다

 

작은 행렬의 합을 구하는 것도 이중 포문을 사용하기 때문에 총 4개의 반복문이 중첩된다. => 시간복잡도 O(n^4)

 

작성코드

#import sys
#sys.stdin = open("input.txt", "r")

T = int(input())
for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    matrix = [[0] for _ in range(N)]
    for i in range(N):
        matrix[i] = list(map(int, input().split()))

    max = 0
    for r in range(N-M+1):
        for c in range(N-M+1):
            sum = 0
            for rt in range(M):  #row of temp (temp: M*M)
                for ct in range(M):
                    sum += matrix[r+rt][c+ct]
            if max < sum:   max = sum
            
    print(f'#{test_case} {max}')

 

제출결과 실행시간은 160 ms 였다.