[Prefix Sum] BOJ 20002 사과나무

 

🎈 백준 20002 사과나무

www.acmicpc.net/problem/20002

20002번: 사과나무

 

❗ 문제의 핵심, 풀이 과정

• N × N 크기의 정사각형 모양 과수원이 있고, 형곤이는 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있다.

• 나무의 위치를 좌표로 하여, 총이익이 2차원 배열의 형태로 주어진다.

• 형곤이가 사과나무를 K × K 의 크기의 정사각형 모양으로 가져갈 때 최대 총이익을 구해야 한다.

 

=> 1~K 까지의 정사각형을 설정하고 과수원 범위만큼 완전탐색하여 최대 총이익을 구할 수 있다.

=> 또한, Prefix Sum을 이용하여 효율적으로 구현할 수 있다.

 

 

pre[i][j]에 (0,0)~(i, j) 까지의 구간합을 구한다. arr[i][j]는 주어진 2차원 배열의 총이익이다.

pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + arr[i][j]

 

 

과수원 범위 안에서 시작점(i, j), 끝점이(i+k, j+k)인 정사각형의 총이익

profit = pre[i+k][j+k] - pre[i-1][j+k] - pre[i+k][j-1] + pre[i-1][j-1]

 

✅ 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
pre = [[-1001]*(n+1) for _ in range(n+1)]

# (i, j)까지의 구간합 구하기
for i in range(1, n+1):
    arr = list(map(int, input().split()))
    for j in range(1, n+1):
        pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + arr[j-1]

max_profit = pre[0][0]
# 정사각형으로 자른다.
for k in range(n):
    for i in range(1, n-k+1):
        for j in range(1, n-k+1):
            # 시작점을 시작점(i, j), 끝점이(i+k, j+k)인 정사각형의 총이익
            profit = pre[i+k][j+k] - pre[i-1][j+k] - pre[i+k][j-1] + pre[i-1][j-1]
            max_profit = max(max_profit, profit)    # 최대 총이익 업데이트

print(max_profit)