Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save inspirit941/01ee7d8d19ac4d19b23fc1db2796cb40 to your computer and use it in GitHub Desktop.
Save inspirit941/01ee7d8d19ac4d19b23fc1db2796cb40 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment