[SWEA] <D2> 2001 - 파리 퇴치

문제

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

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!

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

---

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
다음 N 줄에 걸쳐 N x N 배열이 주어진다.

문제

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

제약 사항

1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

---

예제 입력 1

10
5 2
1 3 3 6 7
8 13 9 12 8
4 16 11 12 6
2 4 1 23 2
9 13 4 7 3
6 3
29 21 26 9 5 8
21 19 8 0 21 19
9 24 2 11 4 24
19 29 1 0 21 19
10 29 6 18 4 3
29 11 15 3 3 29
...

예제 출력 1

#1 49
#2 159
...

---

해결 방법

음... 왜 이렇게 풀었는지 기억이 잘 안나지만... 누적합을 통해서 답을 구했다

앞부분에서 숫자를 입력받을 때, 누적합을 바로 구해서 리스트에 넣어주엇다. 

t = int(input())
 
def inRange(x,y,n,m):
    return 0 <= x+m-1 < n and 0 <= y+m-1 < n
 
for test_case in range(1, t+1):
    n,m = map(int,input().split())
    prefix_list = []
    for i in range(n):
        numbers = list(map(int,input().split()))
        row = [0]
        temp = 0
        for number in numbers:
            temp += number
            row.append(temp)
        prefix_list.append(row)
         
    answer = -1
    for x in range(n): 
        for y in range(n):
            if inRange(x,y,n,m):
                current = 0
                for k in range(y,y+m):
                    current += (prefix_list[k][x+m] - prefix_list[k][x])  
                if current > answer:
                    answer = current
    print("#{} {}".format(test_case, answer))

 

누적합을 사용하지 않고 아래와 같이 M x M 영역의 바로 계산해서 구할 수도 있다.

T = int(input())
 
def inRange(x, y, n, m):
    return x+m-1 < n and y+m-1 < n  # M x M 영역이 배열 안에 완전히 들어가는지 확인
 
for test_case in range(1, T+1):
    N, M = map(int, input().split())
     
    # N x N 배열 입력 받기
    arr = [list(map(int, input().split())) for _ in range(N)]
     
    max_sum = 0
    # 가능한 모든 시작점에 대해
    for i in range(N):
        for j in range(N):
            if inRange(i, j, N, M):
                current = 0
                # M x M 영역의 합 계산
                for x in range(i, i+M):
                    for y in range(j, j+M):
                        current += arr[x][y]
                max_sum = max(max_sum, current)
     
    print(f"#{test_case} {max_sum}")