https://www.acmicpc.net/problem/20002
시간 1초, 메모리 512MB
input :
- N(1 ≤ N ≤ 300)
- 해당 나무를 수확했을 때 얻을 수 있는 총이익
output :
- 최댓값을 출력
조건 :
- 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수
과거의 문제 중 1451 번에서 사용한 합을 구하는 방법을 이용해야 하는 문제다.
그런데 그냥 인덱스를 가지고 놀려고 하니 복잡하다고 생각을 하기 시작한건지 그냥 딴 생각을 한 건지... 빙빙 돌다가 겨우 찾았다.
일단 각 좌표까지의 누적합을
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1] + data[i][j] 를 이용해 구하자.
그러나, 현재 우리가 만들어 놓은 리스트의 경우 dp가 1, 1부터 값을 가지고 있게 하고 싶어서
dp[x + 1][y + 1] = dp[x][y + 1] + dp[x + 1][y] - dp[x][y] + data[x][y]
이렇게 해주도록 하자....
그냥 위에꺼는 1, 1 에서 부터 시작하는 거고.
아래 거는 0, 0 부터 시작하는 것이다. 그리고 나는 이 방법을 찾으려고 했었다....
그렇다면 이제 모든 구간을 다 돌면서 최댓값을 찾으면 된다.
구간을 설정했을 때, x와 y가 움직일 수 있는 구간은 어디 까지 인지가 관건인데.
x + i(구간) <= n 이면 된다. 그래서 이를 x < n + i + 1 로 바꿔주었다.
import sys
n = int(sys.stdin.readline())
data = []
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
temp = list(map(int, sys.stdin.readline().split()))
data.append(temp)
for x in range(n):
for y in range(n):
dp[x + 1][y + 1] = dp[x][y + 1] + dp[x + 1][y] - dp[x][y] + data[x][y]
ans = -99999
for i in range(1, n + 1):
for x in range(n - i + 1):
for y in range(n - i + 1):
nx = x + i
ny = y + i
ans = max(ans, dp[nx][ny] - dp[nx][y] - dp[x][ny] + dp[x][y])
print(ans)구간은 전체 정사각형이 될 수 있음을 기억하자.
