[프로그래머스] 서울에서 경산까지.py

from collections import defaultdict
def solution(K, travel):
    # dfs(0, travel, K, 0, 0)
    # table[n][key] = n번째 도시를 key의 시간으로 방문할 때 모금액의 최댓값
    answer = 0
    table = [defaultdict(int) for _ in range(100)]
    table[0][travel[0][0]] = travel[0][1] if travel[0][0] <= K else 0
    table[0][travel[0][2]] = travel[0][3] if travel[0][2] <= K else 0
    for n in range(1, len(travel)):
        for key in table[n-1]:
            # 도보이동이 가능한 경우
            if key + travel[n][0] <= K:
                table[n][key + travel[n][0]] = max(table[n][key+travel[n][0]], table[n-1][key] + travel[n][1])
                answer = max(answer, table[n][key+travel[n][0]])
            # 자전거 이동이 가능한 경우
            if key + travel[n][2] <= K:
                table[n][key+travel[n][2]] = max(table[n][key+travel[n][2]], table[n-1][key] + travel[n][3])
                answer = max(answer, table[n][key+travel[n][2]])
    return answer