[백준/Python] 14430번 : 자원 캐기

문제

https://www.acmicpc.net/problem/14430

14430번: 자원 캐기

---

풀이

다이나믹 프로그래밍으로 풀이

편하게 작성하기 위해 N+1행 M+1열인 0으로 이루어진 2차원 리스트 생성한다.

이중 반복문을 통해 1,1부터 N,M까지 dp에 값(해당 위치까지의 최댓값)을 넣어준다.

(NXM을 입력받았으므로 [i-1][j-1]에 해당하는 값에 dp로 구한 위쪽[i-1][j]과 왼쪽[i][j-1] 중 큰 값을 더한다.)

최댓값인 오른쪽 아래의 값을 출력한다.

ex) 5행 4열 입력값                    
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0

dp 결과
0 0 0 0 0
0 0 1 1 1
0 0 1 2 2
0 1 2 2 2
0 2 2 2 3
0 3 4 4 4

---

코드

n, m = map(int, input().split())
li = [[*map(int, input().split())] for _ in range(n)]
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = li[i-1][j-1] + max(dp[i-1][j], dp[i][j-1])

print(dp[-1][-1])