[Python 3] BOJ - 14863 "서울에서 경산까지"

 # 문제 링크

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

14863번: 서울에서 경산까지

 

 # 풀이

 개인적으로 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 주어진 문제에서 시간을 무게라고 생각하면 냅색문제와 완전히 동일한 문제가 된다. 따라서 상태 공간은 현재 idx번째 경로에서 남은 시간이 total일 때, 얻을 수 있는 최대 모금액이며 dp[idx][total]가 된다

 그런데 시간이 음수가 될 수는 없으므로 만일 현재 시간이 음수이면 -INF를 리턴하면 정답을 구할 수 있다

 

 # 코드

import sys

# go : 현재 idx번째 경로에서 남은 시간이 total일 때 얻을 수 있는 최대 모금액을 리턴하는 함수
def go(idx, total):
    # 시간 예외 처리
    if total < 0:
        return -9876543210
    # Base case : 경산까지 도달한 경우
    if idx == n:
        return 0
    # Memoization
    if dp[idx][total] != -1:
        return dp[idx][total]
    # 점화식
    dp[idx][total] = max(go(idx + 1, total - arr[idx][0]) + arr[idx][1], go(idx + 1, total - arr[idx][2]) + arr[idx][3])
    return dp[idx][total]

# 입력부 및 정답출력
n, k = map(int, sys.stdin.readline().split())
dp = [[-1] * (k + 1) for _ in range(n)]
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
print(go(0, k))