https://www.acmicpc.net/problem/11048
시간 1초, 메모리 256MB
input :
output :
조건 :
처음엔 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])