[SWEA] 2001. 파리 퇴치 (DP)

✍️ 문제 요약

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE

SW Expert Academy

 

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

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 할 때, 죽은 파리의 개수를 구하여라.

 

💪 무식하게 풀기 (반복문)

정사각형의 시작 점을 (i, j)로 두고 모든 경우에서 합을 구한다.

무려 4중 for문이다..😱 문제에서 N 은 5 이상 15 이하이기 때문에 무리 없이 테스트 케이스는 통과한다.

import sys
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")

# 보드(B)에서 (x, y)부터 한 변의 길이가 size인 정사각형 합
def calc(B, x, y, sz):
    tot = 0
    for i in range(x, x+sz):
        for j in range(y, y+sz):
            tot += B[i][j]
    return tot

if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T + 1):
        N, M = map(int, input().split())
        board = [list(map(int, input().split())) for _ in range(N)]

        mx = -1e9
        for i in range(N-M+1):
            for j in range(N-M+1):
                mx = max(mx, calc(board, i, j, M))

        print('#{} {}'.format(test_case, mx))

 

✨ 우아하게 풀기 (DP)

N*N배열에서, M*M의 부분합이 가장 큰 구간을 찾는 문제
부분합은 뭐다? DP다

1) 부분 합(`total`) 미리 구해놓기

 

2) 주어진 범위에서 정사각형 합 구하기

 

직사각형 배열에서 어느 부분이 중복 계산될 지 체크하면 풀 수 있는 문제!

O(n^2)의 시간복잡도 안에 해결 가능하다.

import sys
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")

if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T + 1):
        N, M = map(int, input().split())
        board = [list(map(int, input().split())) for _ in range(N)]
        tot = [[0] * N for _ in range(N)] # (0,0)~(n,n)의 직사각형 합을 저장하는 total 리스트

	# 부분합 미리 구해놓기
        for i in range(N):
            for j in range(N):
                tot[i][j] = board[i][j]
                if i>0:
                    tot[i][j] += tot[i-1][j]
                if j>0:
                    tot[i][j] += tot[i][j-1]
                if i>0 and j>0:
                    tot[i][j] -= tot[i-1][j-1]

	# 주어진 범위에서 정사각형 합 구하기
        mx = -1e9
        for i in range(N-M+1):
            for j in range(N-M+1):
                # 이때 (i, j)는 정사각형 시작점
                ii, jj = i+M-1, j+M-1 # (ii, jj)는 정사각형 끝점
                if i==0 and j==0:
                    tmp = tot[ii][jj]
                elif i==0:
                    tmp = tot[ii][jj] - tot[ii][jj-M]
                elif j==0:
                    tmp = tot[ii][jj] - tot[ii-M][jj]
                else:
                    tmp = tot[ii][jj] - tot[ii][jj-M] - tot[ii-M][jj] + tot[ii-M][jj-M]
                mx = max(mx, tmp)

        print('#{} {}'.format(test_case, mx))

 

🔗 참고

SWEA 2001번: 파리 퇴치/DP