[Python][백준][11048] 이동하기 (DP)

🍋 문제링크

www.acmicpc.net/problem/11048

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 37064KB

시간 : 1000ms

🍉 Code

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
dp = [[0] * (M + 1)] * (N + 1)
candy = []

for i in range(N):
    candy.append(list(map(int, input().split())))

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

print(dp[N][M])

🥝 메모

<문제 접근>

dp[N][M] 를 구할 수 있는 경우의 수는 총 3가지로

• dp[N-1][M] + candy
• dp[N][M-1] + candy
• dp[N-1][M-1] + candy

위의 경우 들을 모두 구해서 그 중의 가장 큰 값을 dp[N][M]로 결정하면 된다

<python : 2차원 배열 입력받기>

for i in range(N): 
	arr.append(list(map(int, input().split())))