[dp/백준] 11048번: 이동하기

-문제: https://www.acmicpc.net/problem/11048

비교적 쉽게 점화식을 구할 수 있었던 문제였다. 

(i,j)를 기준으로 뻗어나는것((i+1,j),(i,j+1),(i+1,j+1))을 생각하는게 아니라, (i,j)를 기준으로 몰리는 숫자들( (i-1,j),(i,j-1),(i-1,j-1))을 생각해야한다. 

dp를 풀면서 깨달은 것은 시작점을 기준으로 생각하는 것이 아닌, 끝나는 점을 기준으로 생각해야지 정답에 가까운 것 같다. 

 

점화식은 

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

 

근데 i==0,j==0인 경우는 숫자가 유입되는 경로가 하나라서 이를 따로 설정해야하나 싶었는데 dp에 행+1,열+1을 하면 data에서 0번째 행과 0번째 열들도 세가지 경로로 숫자를 더할 수 있다. 

2트만에 맞은 문제인데, 이전에 풀었을 때는 엄청 많이 시도했었는데, 이번에는 2번만에 맞으니까 발전한게 눈에 보였다. 

-정답 풀이: 

n,m=map(int,input().split())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
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]=data[i-1][j-1]+max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
print(dp[n][m])