https://www.acmicpc.net/problem/11048
시간 1초, 메모리 256MB
input :
- N, M(1 ≤ N, M ≤ 1,000)
- (r, c)에 놓여져 있는 사탕의 개수이다. (0 <= 사탕의 개수 <= 100)
output :
- (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력
조건 :
- 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다.
- 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.
처음엔 BFS를 이용해서 dp 배열에 각 사탕의 최대 갯수를 저장하도록 하려 했다. 그런데
2 2
0 0
0 5
이러한 경우를 따지기 위해서 graph[nx][ny] + dp[x][y] >= dp[nx][ny] 에도 q에 추가를 할 경우에 시간초과가 발생하게 된다......
그래서.. dp로 가자.
일단... 대각선으로 이동하는 경우는 제껴도 된다.
어차피 대각선으로 이동하는 것보다, 오른쪽 -> 아래쪽으로 이동하는 것이 기대값이 더 크기 때문이다.
그래서 dp의 점화식이 아래와 같이 된다.
dp[i][j] = graph[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1])그리고, dp[n][m]의 값을 출력해주자.
import sys
n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
graph.append(list(map(int, sys.stdin.readline().split())))
dp = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = graph[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1])
print(dp[n][m])
