한 번 곡괭이를 사용할 때마다 5번씩 광물을 캐므로, 5개 한세트씩으로 광물 리스트를 묶어주자. 또한 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복해야 하므로, 최대 탐색 길이는 (picks의 합, 수정된 광물 리스트) 중 더 작은 값이 된다.
어떠한 지점에서 남은 곡괭이 종류들에 대해, 그 지점에서의 곡괭이 종류에 따른 피로도를 각각 계산하고 그 중 최소를 구하는 것이 핵심이며, 나는 이를 dfs로 구현하였다.
init : 광물 리스트 minerals를 계산상 편의를 위해 숫자로 바꿔준다.
generate_mineral_list : 광물 리스트 minerals를 연속된 5개 지점마다 묶는다. 5개 지점 내에서는 순서가 사실상 상관이 없으므로 [diamond, iron, stone]의 꼴로 바꾸어 줄 수 있다. 이렇게 만들어진 새로운 광물 리스트를 반환한다.
cal_cost : 특정 곡괭이로 원소가 [diamond, iron, stone]의 꼴인 리스트에 대해 이 때 소요되는 피로도를 반환한다.
dfs : 경로 탐색 함수. DFS를 수행하며 최소 피로도를 재귀적으로 탐색 후 반환한다.
solve : 메인함수. init과 generate_mineral_list를 통하여 가공된 minerals 리스트와, 앞선 정의에 따른 최대 탐색 길이를 함께 dfs 함수에 삽입하여 결과를 도출, 이를 반환한다.
풀이 코드
mineral_dict = {
'diamond' : 0,
'iron' : 1,
'stone' : 2
}
cost_mat = [
[1, 1, 1],
[5, 1, 1],
[25, 5, 1]
]
def init(minerals) :
minerals = [mineral_dict[mineral] for mineral in minerals]
return minerals
def generate_mineral_list(minerals) :
result = list()
tmp = [0]*3
for i in range(0, len(minerals), 5) :
for j in range(5) :
if i + j >= len(minerals) :
break
tmp[minerals[i+j]] += 1
result.append(tmp)
tmp = [0]*3
return result
def cal_cost(pick, mineral) :
return sum([ cost_mat[pick][i] * mineral[i] for i in range(3) ])
def dfs(idx, picks, minerals, cost, max_idx) :
if idx == max_idx :
return cost
result = float('inf')
for i in range(3) :
if picks[i] == 0 :
continue
picks[i] -= 1
next_cost = cost + cal_cost(i, minerals[idx])
result = min(result, dfs(idx+1, picks, minerals, next_cost, max_idx))
picks[i] += 1
return result
def solution(picks, minerals):
minerals = init(minerals)
minerals = generate_mineral_list(minerals)
max_idx = min(sum(picks), len(minerals))
answer = dfs(0, picks, minerals, 0, max_idx)
return answer
