문제 링크
풀이 과정
전체 코드
•
첫 번째 방법 → 완전 탐색 (재귀)
def solution(picks, minerals):
fatigues = {
0: {"diamond": 1, "iron": 1, "stone": 1}, # 다이아몬드
1: {"diamond": 5, "iron": 1, "stone": 1}, # 철
2: {"diamond": 25, "iron": 5, "stone": 1} # 돌
}
fatigue_min = 1e+8
def bfs(picks, minerals, fatigue):
nonlocal fatigue_min
# base case
if (sum(picks) == 0) or (len(minerals) == 0):
if fatigue < fatigue_min: fatigue_min = fatigue
return
# 반복 코드 -> 곡괭이로 광물을 캐고, 피로도를 증가시킨다.
for idx in fatigues.keys():
if picks[idx] >= 1:
picks_copied = picks.copy()
picks_copied[idx] -= 1
bfs(
picks_copied,
minerals[5:],
fatigue + sum([fatigues[idx][mineral] for mineral in minerals[:5]])
)
bfs(picks, minerals, 0)
return fatigue_min
Python
복사
•
두 번째 방법 → 정렬
def solution(picks, minerals):
minerals = minerals[:sum(picks)*5]
mineral_sets = [[0, 0, 0] for _ in range(10)]
answer = 0
for idx, mineral in enumerate(minerals):
if mineral == 'diamond': mineral_sets[idx//5][0] += 1
elif mineral == 'iron': mineral_sets[idx//5][1] += 1
else: mineral_sets[idx//5][2] += 1
mineral_sets = sorted(mineral_sets, key=lambda x: (-x[0], -x[1], -x[2]))
for dias, irons, stones in mineral_sets:
if picks[0] >= 1: # 다이아몬드 곡괭이가 있는 경우
answer += (dias + irons + stones)
picks[0] -= 1
elif picks[1] >= 1: # 철 곡괭이가 있는 경우
answer += (5*dias + irons + stones)
picks[1] -= 1
else:
answer += (25*dias + 5*irons + stones)
picks[2] -= 1
return answer
Python
복사