풀이

1. 각 곡괭이로 캐면서 소모되는 피로도를 dict로 정리한다.
   • 예를 들어, 5번씩 캘 수 있으니, 전체 광물이 13개가 있다면, dia의 dict는 [5,5,3]이 되는것이다.
   • 다이아 곡괭이의 수를 일단 무시하고 캐는데 소모되는 피로도만 전부 넣어준다.
   • 마찬가지로 다른 곡괭이들도 갯수를 무시하고 각 5개씩 캐는데 쓰이는 피로도를 넣어준다.
     
   • 이 input 값으로 dict를 정리하면,
     • dict['diamond'] = [5, 3]
     • dict['iron'] = [17, 7]
     • dict['stone'] = [85, 31]
     • 다이아로 처음 5개 캐는데 걸리는 피로도는 5, 나머지 3개 캐는데 3
     • 철로 처음 5개 캐는데 5+5+5+1+1 = 17, 나머지 3개는 5+1+1
     • 돌로 처음 5개 캐는데 25+25+25+5+5 = 85, 나머지 3개는 25+5+1 = 31
2. 모든 경우의 수를 전부 queue에 집어넣어서 다 캘때까지 걸리는 피로도를 전부 result라는 list에 넣어준다.
   • 어차피 picks의 길이는 3개이며, 각 최대 갯수는 5개이다.
   • 5^3 = 125개이다. 왜냐면 곡괭이를 다 쓰면 광석이 남아있더라도 더 캘 수 없기 때문에 최대 125개밖에 실행을 안한다.
3. result에 담겨져 있는 각 피로도 중에 최소값을 return 해준다.

코드

from collections import defaultdict, deque

def solution(picks, minerals):
    ls_dict = defaultdict(list)
    count_dia = 0
    count_iron = 0
    count_stone = 0
    for index in range(len(minerals)):
        if index == 0:
            pass
        elif index % 5 == 0:
            ls_dict['diamond'].append(count_dia)
            ls_dict['iron'].append(count_iron)
            ls_dict['stone'].append(count_stone)
            count_dia = 0
            count_iron = 0
            count_stone = 0
        else:
            pass
        count_dia += 1
        if minerals[index] == "diamond":
            count_iron += 5
            count_stone += 25
        elif minerals[index] == "iron":
            count_iron += 1
            count_stone += 5
        else:
            count_iron += 1
            count_stone += 1
    if count_dia != 0:
        ls_dict['diamond'].append(count_dia)
        ls_dict['iron'].append(count_iron)
        ls_dict['stone'].append(count_stone)
        
    q = deque()
    if picks[0] != 0:
        q.append(([picks[0] - 1, picks[1], picks[2]], 1, ls_dict['diamond'][0]))
    if picks[1] != 0:
        q.append(([picks[0], picks[1] - 1, picks[2]], 1, ls_dict['iron'][0]))
    if picks[2] != 0:
        q.append(([picks[0], picks[1], picks[2] - 1], 1, ls_dict['stone'][0]))
    result = list()    
    while q:
        pick, index, cnt = q.popleft()
        
        if index >= len(ls_dict['diamond']):
            result.append(cnt)
            continue
        elif pick[0] == pick[1] and pick[1] == pick[2] and pick[0] == 0:
            result.append(cnt)
            continue
        
        if pick[0] != 0:
            q.append(([pick[0] - 1, pick[1], pick[2]], index + 1, cnt + ls_dict['diamond'][index]))
        if pick[1] != 0:
            q.append(([pick[0], pick[1] - 1, pick[2]], index + 1, cnt + ls_dict['iron'][index]))
        if pick[2] != 0:
            q.append(([pick[0], pick[1], pick[2] - 1], index + 1, cnt + ls_dict['stone'][index]))
                
    return min(result)