[python] 백준 11048번: 이동하기(DP)

# 11048 이동하기

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

11048번: 이동하기

⭐ 코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

candy = [list(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] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + candy[i-1][j-1]

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

📝 풀이

목적지까지 이동하면서 최대한 많은 캔디를 주울 수 있도록 코드를 작성해야한다. 그렇기 때문에 dp리스트를 생성해서 준규가 오른쪽, 아래, 오른쪽 대각선 방향으로 움직일때마다 dp에 기록해주면 된다. DP의 핵심은 점화식인데 위의 조건을 충족하는 점화식을 구하는 것이 핵심이다.

🔓 정답 코드 뜯어보기

N, M = map(int, input().split())

candy = [list(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] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + candy[i-1][j-1]

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

candy가 담긴 리스트와 메모이제이션을 위한 dp 배열을 생성한 뒤, 이중 반복문을 통해서 candy리스트를 탐색시켜준다.

탐색을 하면서 가장 큰 값을 dp에 저장해야 하므로 점화식은 다음과 같다.

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

오른쪽, 아래, 오른쪽아래 대각선을 탐색하면서 가장 큰 값과 이전의 캔디값을 더해서 저장시켜준다. 사실 오른쪽아래 대각선을 가는 것보다 아래 오른쪽, 혹은 오른쪽 아래로 이동하는 것이 무조건 이득이기 때문에 dp[i-1][j-1]은 없어도 된다. 실제로 대각선 이동을 지우고 제출해봤더니 정답으로 인정이 됐다.

최종적으로 마지막 dp리스트에 기록된 dp[-1][-1]값을 출력시켜주면 정답이 된다.