[Python, 파이썬] SWEA 2001. 파리 퇴치

 

 

N x N 크기의 파리의 수가 저장된 배열이 있다 하자.

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

 

배열의 크기 N, 파리채의 크기 M을 입력받았을 때,

파리채로 죽일 수 있는 파리의 수의 최댓값을 구하는 문제다.

 

 

T = int(input()) # 테스트 케이스의 개수 T

for n in range(1, T+1):

    N, M = map(int, input().split()) # 배열의 크기 N, 파리채의 크기 M
    matrix = [] # 빈 배열
    max_num = 0

    # 배열에 값 저장
    for i in range(N):
        matrix.append(list(map(int, input().split())))

    # 파리채 크기 구하기 
    for i in range(N-M+1):
        for j in range(N-M+1):

            temp = 0
            
            for k in range(i, i+M): # 파리채의 크기 M
                temp += sum(matrix[k][j:j+M]) # 파리 저장
            
            max_num = max(max_num, temp) # 최대 파리 비교
        
    print("#%d %d" %(n, max_num))

 

 

[문제풀이]

---

N x N 배열 안의 모든 M x M 크기의 구간을 구해 그 구간의 최댓값을 구하는 문제다.

 

1) 누적합 알고리즘

2) 4중 for문

 

N의 크기도 5에서 15 사이로 크지 않아 누적합을 굳이 쓰지 않아도 4중 for문으로 쉽게 풀린다.