[백준] 20002 사과나무

문제

• 사과 나무를 수확했을 때 얻을 수 있는 최대 이익 구하기
• NxN 크기의 과수원 모든 칸에는 사과나무가 심겨져 있고, 각 사과나무를 수확할 때 얻을 수 있는 이득은 각기 다르다.
• 농부는 KxK 모양의 땅에서만 수확해갈 수 있다.
  • 1 <= K <= N <= 300
  • -1000 <= 사과나무 수확 시 이익 <=  1000

 

풀이

• 시간 복잡도 : N이 300이기 때문에 $O(N^3)$까지 가능하다.
  • 아주 간단하게, K가 1~N까지고, 각 위치에서의 (N*N개) 합을 구한다면 (N*N) => 시간 초과..
  • 누적합으로 합 구하는 시간을 단축시켜야 한다.
• 누적합 구하기 : 행과 열 누적합을 구했을 때, 정사각형이므로 포함되지 않은 부분을 제외해줘야 한다.

• pypy로 해야 시간초과 안남

 

N = int(input())

# 정사각 크기의 누적합
prefix = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    data = list(map(int, input().split()))
    for j in range(1, N+1):
        prefix[i][j] = prefix[i][j-1] + prefix[i-1][j] - prefix[i-1][j-1] + data[j-1]

answer = -1001
for k in range(N):
    for r in range(1, N-k+1):      # row
        for c in range(1, N-k+1):  # col
            # (r, c) ~ (r+k, c+k) 정사각형일 때
            answer = max(answer, prefix[r+k][c+k] - prefix[r-1][c+k] - prefix[r+k][c-1] + prefix[r-1][c-1])

print(answer)

 

References

• 백준 20002번
• 2023.05.05 오늘의 문제