백준 14430 자원 캐기 / python

문제 : 14430

풀이 point

로봇은 오른쪽 또는 아래쪽으로 한칸 만 움직일 수 있다.

다이나믹프로그래밍을 통해 i번째 행 j번째 열일 때 왼쪽 혹은 오른쪽의 최대값 + 자원 개수를 파악하면 된다.

점화식으로 나타나면 이런 형식이 된다.
dp는 다이나믹프로그래밍 저장 배열, grid는 입력받은 자원 지도, i&j는 i행 j열을 의미한다.

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

풀이 코드

#백준, 14430 자원 캐기

N, M = map(int, input().split())

grid = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*(M+1) for _ in range(N+1)]

for i in range(N):
    for j in range(M):
        dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])

print(max(map(max, dp)))

사족

dp의 가장 중요한 풀이 point는 어떤 특정 부분을 구하기 위해 어디까지 알고 있으면 되는가?를 생각하면 될 것 같다. 더 간단하게 말하자면

누군가 N-1까지만 구해놓으면 N은 구해놓은 N-1 + ? 특정값만 해주면 되겠구나.

이런 사고방식에 익숙해져야할 것 같다.
바로 점화식을 찾으려하면 오히려 머리가 아픈 느낌...