Python 11048번 이동하기

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

11048번: 이동하기

 

이 문제는 dp를 이용하면 쉽게 문제를 풀 수 있다.

문제에 나와있는데 r+1,c 이런것들을 dx와 dy를 이용해서 표현하였고

dp를 이용해서 전에 있던 값에 이동한 칸의 값을 더한 게 원래 있던 dp값보다 크면 바꾸고 아니면 그대로 유지하도록 했다.

 

import sys
cnt=[]
input=sys.stdin.readline
n,m = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
dx=[1,0,1]
dy=[0,1,1]
dp[0][0]=ary[0][0]
for i in range(n):
    for j in range(m):
        for idx in range(3):
            y=dy[idx]+j
            x=dx[idx]+i
            if 0<=y<m and 0<=x<n:
                dp[x][y]=max(dp[i][j]+ary[x][y],dp[x][y])

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

# python3도 정답 처리가 되긴하는데 반복문이 많을때는 pypy가 더 빨리 처리된다고 한다!