문제 출처 : [SWEA] 2001 파리퇴치

문제

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

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

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

제약 사항

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

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

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

입력

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

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

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

출력

테스트 케이스 t에 대한 결과는 “#t”을 찍고, 한 칸 띄고, 정답을 출력한다.

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

코드

T = int(input())
for tc in range(1, T + 1):
    # N : 총 영역 크기, M : 파리채의 크기
    N, M = map(int, input().split())
    num_list = [list(map(int, input().split())) for _ in range(N)]

    max_val = 0     # 최댓값을 저장할 변수

    # 인덱스를 벗어나지 않도록 범위 지정
    for i in range(N - M + 1):
        for j in range(N - M + 1):
            sum_val = 0     # 파리채 영역 내부의 합을 구할 변수
            # 파리채 크기 만큼 반복하면서 더해줌
            for k in range(M):
                for q in range(M):
                    sum_val += num_list[k + i][q + j]
            # 최댓값 보다 파리채 영역이 더 크면 최댓값 변수에 저장
            if max_val < sum_val:
                max_val = sum_val

    print(f'#{tc} {max_val}')

풀이 방법

파리채의 범위를 설정하는 것과 전체 범위를 설정하는 것이 조금 헷갈렸다. 그래서 처음엔 인덱스 에러가 발생했다. 전체 범위를 N-M+1 로 지정해서 풀이하니까 에러를 해결할 수 있었다.
파리채 영역을 돌면서 해당 영역의 합을 구하고 최대값 변수에 저장된 값과 비교하여 최대값을 구했다.