[백준/python] 백준 자원캐기

문제

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

14430번: 자원 캐기

---

Algorithm

인공지능 WOOK은 오른쪽(r, c+1)과 왼쪽(r+1, c) 방향으로만 움직일 수 있다.
따라서, 현재 위치와 이전에 기록해둔 최댓값을 이용한다. 즉, DP의 Memoization을 활용하여 풀이한다.주의할 점은 인덱싱이다. 가장 윗줄과 왼쪽줄은 먼저 채워주고, 1부터 n까지 기록하도록 한다.

---

Code

n,m=map(int,input().split())

scope=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(m)] for _ in range(n)]
dp[0][0] = scope[0][0]

# 가장 윗줄 채워주기
for i in range(m):
    dp[0][i] = dp[0][i-1] + scope[0][i]
    
# 가장 왼쪽줄 채워주기
for i in range(n):
    dp[i][0] = dp[i-1][0] + scope[i][0]

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

ans=0
for item in dp:
    ans = max(ans, max(item))

if n == 1 and m == 1 and scope[0][0] == 1:
    print(1)
else:
    print(ans)