[백준 20002 / Python] 사과나무

사과나무

🔍 알고리즘 분류

• 누적합

💡 문제 풀이

1. 2차원 배열 범위를 (N+1)(N+1)로 늘리고 첫 행, 첫 열을 모두 0으로 채우기
2. 2차원 누적합 생성
3. 2차원 배열을 순회하며 시작점을 설정하고, K를 1부터 N까지 늘리면서 누적합 계산
4. 최댓값으로 정답 갱신

📄 코드

• Python

import sys
input = sys.stdin.readline

n = int(input())
# 첫 행, 첫 열 0으로 패딩주기
arr = [[0] * (n + 1)]
for _ in range(n):
    arr.append([0]+list(map(int, input().split())))

# 누적합 생성
prefix_sum = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    prefix_sum[i][1] = prefix_sum[i - 1][1] + arr[i][1]

for j in range(1, n + 1):
    prefix_sum[1][j] = prefix_sum[1][j - 1] + arr[1][j]

for i in range(2, n + 1):
    for j in range(2, n + 1):
        prefix_sum[i][j] = arr[i][j] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]

answer = -int(1e9)

for i in range(1, n + 1):
    for j in range(1, n + 1):
        # 정사각형 사이즈 1부터 늘리기
        for k in range(1, n + 1):
            x1, y1, x2, y2 = i, j, i + k - 1, j + k - 1
            # 범위 벗어나면 무시
            if x2 > n or y2 > n:
                continue
            # 누적합 계산
            total = prefix_sum[x2][y2] - prefix_sum[x1 - 1][y2] - prefix_sum[x2][y1 - 1] + prefix_sum[x1 - 1][y1 - 1]
            # 최댓값 갱신
            answer = max(answer, total)

# 정답 출력
print(answer)

• 시간복잡도: O(N^3)