SWEA - 파리 퇴치(2001)

SW Expert Academy

 

문제

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

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!
예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.
 

[제약 사항]
1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

 

 

접근방식

arr라는 빈 배열에 파리개수를 넣음

N = 5, M = 2이면 arr[0][0], arr[0][1], arr[1][0], arr[2][0]을 다 더함

그리고 열의 인덱스를 하나 추가해 arr[0][1], arr[0][2], arr[1][1], arr[1][2]를 더함

이런식으로 arr[0][3], arr[0][4], arr[1][3], arr[1][4]까지 더함. 더 이상 열의 인덱스를 추가할 수 없으므로 행의 인덱스를 하나 추가함

arr[1][0], arr[1][1], arr[2][0], arr[2][1]을 더해주고 여기도 위와 마찬가지로 더이상 열의 인덱스를 추가할 수 없을 때까지 진행

이러한 과정을 행의 인덱스를 더 추가할 수 없을 때 까지 진행

행과 열의 범위는 입력값 N-M+1이 됨(ex: N=5, M=2이면 N-M+1=4까지니까 0~4이므로 범위는 0,1,2,3이 됨)

 

행과 열의 범위를 for문으로 돌리고 그 안에 flies라는 변수를 0으로 선언

그리고 M의 크기만큼 배열들의 각 값을 더해야하니까 y, z라는 변수로 for문을 M만큼 두 번 돌리면서

flies 변수에 값들을 더해줌

 

 

코드

T = int(input())
for i in range(1, T+1):
    N, M = input().split(" ")
    arr = []
    ans_arr = []
    for j in range(0, int(N)):
        nums = list(map(int, input().split()))
        arr.append(nums)
    for k in range(0, int(N)-int(M)+1):
        for x in range(0,int(N)-int(M)+1):
            flies = 0
            for y in range(int(M)):
                for z in range(int(M)):
                    flies += arr[k+y][x+z]
            ans_arr.append(flies)
    print('#'+str(i), max(ans_arr))