1. 문제
2. 풀이
from collections import Counter
costs = [[1,1,1],[5,1,1],[25,5,1]]
index = {'diamond' : 0,'iron': 1,'stone': 2}
answer = []
def dfs(picks, minerals, total_cost):
if sum(picks) == 0 or not minerals:
return answer.append(total_cost)
mineral_counts = Counter(minerals[:5])
available_index = []
for i, pick in enumerate(picks):
if pick != 0:
available.append(i)
for i in available_index:
cost = 0
for key, value in mineral_counts.items():
cost += value * costs[i][index[key]]
picks[i] -= 1
dfs(picks, minerals[5:], cost + total_cost)
picks[i] += 1
def solution(picks, minerals):
dfs(picks, minerals, 0)
return min(answer)3. 로직
특정 곡괭이를 사용하여 광물을 채굴할 때 필요한 최소 피로도를 찾는 깊이 우선 탐색 (DFS) 알고리즘을 구현하였다.
1. 모든 곡괭이가 다 사용되었거나 모든 광물을 다 캔 경우, 지금까지의 곡괭이 조합으로 광물을 캐면서 누적된 피로도를 리스트에 추가시킨다.
2. 광물은 주어진 순서대로만 캘 수 있으며 하나의 곡괭이로 다섯 개의 광물을 캘 수 있다.
- minerals 배열에서 순차적으로 5개의 원소만 가져온다.
- Counter 클래스를 활용하여 각 광물의 종류와 해당 광물이 얼마나 남아 있는지를 계산한다.
3. available_index 리스트는 아직 사용 가능한 곡괭이가 있는 인덱스를 저장하는 리스트다. 즉, 해당 곡괭이 종류를 더 이상 사용할 수 없을 때는 해당 인덱스가 리스트에 포함되지 않는다.
4. available_index 리스트를 순회하며 현재 곡괭이로 광물을 얻는 데 필요한 비용을 계산한다.
5. 현재 사용 중인 곡괭이의 개수를 감소시키고, 업데이트된 상태 (남은 곡괭이 및 남은 광물) 와 현재까지의 비용을 사용하여 dfs 함수를 재귀적으로 호출한다.
- 재귀 호출 이후에 곡괭이 개수를 다시 복구한다.
6. DFS 탐색이 완료되면 answer 리스트에 저장된 최소 피로도를 반환한다.
