[파이썬/python] 백준 - 20002 사과나무

문제

https://www.acmicpc.net/problem/20002

---

문제 설명

1. N*N 크기의 정사각형 모양 과수원이 있고, N*N개의 사과나무가 1*1 크기의 간격으로 모든 칸에 심어져있다.
2. 사과를 수확하려면 K*K크기의 정사각형 모양으로만 수확이 가능하다.
   1. 이 때 K는 1 <= K <= N 범위를 가진다.
3. 2차원 배열의 형태의 이익 + 노동비의 값이 주어질 때얻을 수 있는 최대 총이익을 구한다.

 

---

풀이

이 문제는 밭에서 특정 범위의 정사각형의 점수의 총합을 구하는 문제이다.

1번 예제를 통해 문제를 이해해 보자.

4
-1 -2 -3 -4
5 6 7 8
9 10 11 12
-13 -14 -15 -16

 

1번 예제는 이와 같이 3*3 크기로 잘라야 최대 값인 45가 나오게 된다.

하지만 이러한 크기가 아니더라도 1*1, 2*2, 3*3, 4*4의 모든 정사각형이 정답의 후보가 된다.

 

하지만 이러한 경우의 수를 모두 구하게 될 때 시간복잡도를 구해보자.

최악의 경우 배열의 크기는 300*300이다.

따라서 정사각형의 개수는

1*1 = 300*300개 * 300(개수 합)

2*2 = 299*299* 299

....

300*300 = 1*1*1개

 

즉 $(1^3+2^3 +... 300^3)$의 연산이 필요하다. 딱 봐도 1초는 충분히 넘길만한 수치이다.

 

따라서 연산 속도를 획기적으로 줄이기 위해 누적합 알고리즘을 사용했다.

위 이미지의 파란색 네모의 합 (4)를 구하려면 (3) - (1) - (2) + (1과 2가 겹치는 부분)을 계산하면 된다.

 

하지만 위 배열은 각 위치의 합을 구한 누적합 배열이 아니다. 따라서 우리는 누적합 배열을 따로 구해야 한다.

 

현재 위치의 누적합을 구하는 공식은 위에서 본 것과 같다.

 

(현재 위치까지의 누적 합) = prefix [i][j] - prefix [i-1][j] - prefix [i][j-1] + prefix [i-1][j-1]

현재 위치에서 내 이전 행까지와 이전 열까지를 빼 주고, 겹치는 부분인 (i-1, j-1)을 더해주는 것이다.

 

이를 통해 누적합 배열을 만들었다면 위 방식을 통해 모든 정사각형의 조합을 구하면 된다.

 

---

코드

import sys
input = sys.stdin.readline

N = int(input())
INF = sys.maxsize

board = [[0 for _ in range(N+1)]]+[[0] + list(map(int,input().split())) for _ in range(N)]
prefix = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,N+1):
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] + board[i][j] - prefix[i-1][j-1]

res = -INF
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(min(i,j),0,-1):
            res = max(res, prefix[i][j] - prefix[i][j-k] - prefix[i-k][j] + prefix[i-k][j-k])

print(res)

---

시간복잡도

• 모든 정사각형을 구할 때 시간복잡도는 $O(N*N*N)$ 정도이다. (마지막 K는 어림잡아 N으로 계산했다.)
• 최악의 경우 N = 약 300이므로 $O(2*10^7)$의 시간복잡도를 가진다.