[백준/Python] 11048_이동하기

문제

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

11048번: 이동하기

코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
matrix = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    lst = list(map(int, sys.stdin.readline().rstrip().split()))
    for j in range(len(lst)):
        matrix[i][j + 1] = lst[j]  # matrix 입력 받기
dp = [[0] * (m + 1) for _ in range(n + 1)]  # dp 테이블 초기화

for i in range(n + 1):
    for j in range(m + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]  # 점화식
print(dp[-1][-1])

풀이

처음에 문제를 접근할 때 DFS를 이용했지만 시간 초과가 나서 DP를 이용하여 풀었습니다.

DP를 이용하면 이미 왔던 경로를 다시 연산하는 것을 줄일 수 있어서 시간적인 이득이 있습니다.

입력받은 사탕의 개수를 (n+1)*(m+1) 크기의 이차원 배열 matrix 에 저장합니다.

마찬가지로 이차원 dp 테이블을 선언하면 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + matrix[i][j] 의 점화식을 찾을 수 있습니다.

최종적으로, dp[-1][-1]값이 준규가 (n, m)위치로 이동할 때 최대의 사탕 개수입니다.