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

백준 20002 - 사과나무

시간 제한 1초, 메모리 제한 512MB

# 조건

• N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다.
• 농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원 내에 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수라구! 나머지는 내가 먹을께! 하하!" 라고 통보했다.
• 하나의 사과나무를 수확할 때, 사과를 통해 얻을 수 있는 이익과 노동비로 빠져나가는 손해가 동시에 이루어진다.
• 그래서 형곤이는 나무의 위치를 좌표로 하여, 사과를 통해 얻은 이익과 노동비를 더한 총이익을 2차원 배열의 형태로 정리했다.
• 악독한 땅주인 신영이로부터 고통받는 귀여운 형곤이에게 최대 총이익을 안겨주고 싶은 당신, 형곤이를 도와주자!

입력

• 첫 번째 줄에는 과수원의 크기 N이 주어진다. (1 ≤ N ≤ 300)
• 두 번째 줄부터 N + 1번째 줄까지, 해당 나무를 수확했을 때 얻을 수 있는 총이익을 표시한다.
• 총이익은 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

• 첫 번째 줄에 최댓을 출력한다.

# 접근 방법

• 누적합을 이용해서 풀어주면 된다.
• 편의를 위해서 0번행에 1줄, 0번열에 1칸을 채워주어 1, 1부터 사용하게 만들어 주었다.
• 1, 1에서 i, j까지의 누적합을 우선 구해준다.
• 이후에 for k in range(N) 반복문을 추가하여 k * k 크기의 정사각형의 합을 체크한다.
• 1,1에서 시작하지 않는 경우에는 현재 정사각형 좌표 시작점을 r, c라고 했을 때
  • arr[r-1][c+k]와 arr[r+k][c-1]만큼 빼주고
  • 중복되는 구간인 arr[r-1][c-1]만큼 다시 더해주면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

def solve():
    N = int(input())
    arr = [[0] * (N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)]

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

    result = arr[1][1]
    for k in range(N):
        for i in range(1, N-k+1):
            for j in range(1, N-k+1):
                val = arr[i+k][j+k] - arr[i-1][j+k] - arr[i+k][j-1] + arr[i-1][j-1]
                result = max(result, val)

    print(result)

solve()