SWEA[2001] : 파리 퇴치

SWEA[2001] 문제

import sys
sys.stdin=open('input.txt')

T = int(input())

for tc in range(1,T+1):
    n,m = map(int,input().split())
    kill = [list(map(int,input().split())) for _ in range(n)] # N x N 배열

    max_val = 0
    # 앞의 두번의 for문은 MxM 배열의 개수만큼
    for i in range(n-m+1):
        for j in range(n-m+1):
            cnt = 0
            # M*M 배열
            for k in range(m):
                for l in range(m):
                    cnt += kill[i+k][j+l]
            # 최대값 갱신
            if max_val < cnt :
                max_val = cnt

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

이 문제에서 요구하는 사항을 보고 대학교 인공지능 수업에서 들었던 '컨볼루션' 이라는 개념이 생각났다. 이상 쓸데없는 TMI였고, 문제를 살펴보자.

NxN 배열 안에서 MxM 크기의 합이 가장 큰 경우의 값을 구하는 문제이다.

총 4중 for문을 사용했는데, 앞의 2중 for문은 MxM을 하나의 1x1 배열이라고 생각했을 때, (N-M+1)x(N-M+1) 행렬만큼 계산을 해야 된다 .
예시로, N = 5 이고 , M = 2 일 때, 2x2 행렬씩 5x5를 탐색하면 총 (5-2+1) x (5-2+1) 번 연산해야된다.

뒷 부분의 2중 for문은 M*M 배열의 합을 cnt 라는 변수에 저장시키고, max_val보다 cnt값이 크다면 max_val 값을 갱신시켜준다. 이걸
(N-M+1)x(N-M+1) 행렬만큼 반복한다.

그러면 MxM 크기의 합이 가장 큰 경우를 구할 수 있다.