문제풀이/누적합
[Python/파이썬] 백준 20002번 사과나무
딜레이레이
2024. 2. 23. 00:45
20002번: 사과나무
N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다. 농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원
www.acmicpc.net
코드
n = int(input())
profits = [list(map(int, input().split())) for _ in range(n)]
accum = [[0]*(n+1) for _ in range(n+1)] # 누적합
for i in range(1, n+1):
for j in range(1, n+1):
accum[i][j] = accum[i-1][j]+accum[i][j-1] - \
accum[i-1][j-1]+profits[i-1][j-1]
ans = -int(1e9)
for i in range(1, n+1): # 행
for j in range(1, n+1): # 열
for k in range(1, min(i, j)+1): # K x K 정사각형 한 변 길이 K
p = accum[i][j]-accum[i-k][j]-accum[i][j-k]+accum[i-k][j-k]
if p > ans:
ans = p
print(ans)