문제 링크

풀이 과정

전체 코드

• 첫 번째 방법 → 완전 탐색 (재귀)

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

• 두 번째 방법 → 정렬

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