[Python] 프로그래머스. 서울에서 경산까지 (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/42899

프로그래머스

DP문제.

 

table[n][key] = n번째 도시를 key의 시간으로 도착했을 때 얻을 수 있는 수익의 최댓값으로 정의하면

table[n][key]는 table[n-1][key] + n번째 도시에서 얻을 수 있는 비용 중 최댓값이 된다.

 

	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

view raw [프로그래머스] 서울에서 경산까지.py hosted with ❤ by GitHub

2D 리스트보다 효율적으로 만들어보려고 리스트 + dict 자료구조를 썼다.