[Python] 파리퇴치(SWEA 2001번 파이썬)

문제 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

 

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

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

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

 

 

문제 이해

- 2차원 배열을 다루는 완전탐색 문제입니다.

- m*m의 사각형으로 모든 칸을 다 탐색한다고 생각하면 풀이가 수월합니다.

 

문제 풀이

 

문제 이해 중 작성한 메모로 실제 코드와 다름

- 파리채의 크기가 m이기 때문에 실제 n*n의 배열에서 일부만 탐색해야 합니다.

- 파리채의 왼쪽 상단의 점을 기준으로 반복문을 돌며, 따라서 n-m만큼만 탐색해야합니다. range에 적용하려면 n-m+1을 넣어주면 되겠습니다.

- 처음 이중 반복을 통해 한 점에 대해 접근했다면, 이후 또 다른 이중반복을 통해 파리채 내의 각 값들을 순회합니다.

- 파리채 내의 각 값들을 모두 더하여 최댓값이라면 교체합니다.

 

코드

#  swea 2001 파리퇴치
T = int(input())
for test_case in range(1, T + 1):
    n,m = map(int, input().split())
    arr = []
    for i in range(n):
        arr.append(list(map(int,input().split())))
        
    result = 0
    for i in range(n-m+1):
        for j in range(n-m+1):
            all = 0
            for x in range(i, i+m):
                for y in range(j,j+m):
                    all += arr[x][y]
            result = max(result, all)
    print(f'#{test_case}', result)

 

4중 반복문이 등장하긴 하지만, 난이도 자체가 높지 않아서 크게 겁먹을 필요는 없는 것 같습니다.

배열을 사용하는 완전탐색 문제의 경우 이렇게 인덱스로 특별한 아이디어를 요구하는 경우가 많은데, 직관적으로 알아차릴 수만 있으면 쉽게 풀 수 있을 것 같습니다. 이런 직관은 아마 문제를 많이 풀면서 경험적으로 느껴야겠죠?