[Programmers] Level 2. 광물 캐기

🔗 Problem Link

프로그래머스

---

❔Thinking

• 주어진 다이아몬드, 철, 돌 곡괭이로 주어진 광물을 최대한 캘때, 가장 적은 피로도가 쌓이는 방법을 찾는다.
• 곡괭이가 적은 경우 광물이 남을 수 있고, 광물이 적을 경우 곡괭이가 남을 수 있다.

---

💻Solution

1. 모든 경우 확인 (시간초과)

from itertools import permutations
def solution(picks, minerals):
    total_cost = 10e9
    # 곡괭이 선택하기
    need_pick = len(minerals) // 5 + 1
    total_pick = []
    while len(total_pick) <= need_pick:
        cur = -1
        for i in range(3):
            if picks[i] > 0:
                picks[i] -= 1
                cur = i
                break
        if cur == -1:
            break
        total_pick.append(str(cur))
        
    # 피로도 표 만들기
    cost_idx = 0
    cost_nums = [1,1,1,5,1,1,25,5,1]
    costs = dict()
    for a in ['0','1','2']:
        for b in ['diamond','iron','stone']:
            costs[a+b] = cost_nums[cost_idx]
            cost_idx += 1
    # 광물 캐기
    combis = permutations(total_pick, len(total_pick))
    for combi in combis:
        tmp_cost = 0
        idx = 0
        while idx < len(minerals):
            if idx // 5 >= len(combi):
                break
            tmp_cost += costs[combi[idx//5]+minerals[idx]]
            idx += 1
        total_cost = min(total_cost, tmp_cost)
    return total_cost

 

2. 피로도가 높은 조합 (1개의 곡괭이는 5개의 광물을 연속적으로, 모두 캔다)을 다이아몬드로 처리하는 방법

def solution(picks, minerals):
    if sum(picks) * 5 < len(minerals):
        minerals = minerals[:sum(picks)*5]
    
    grouped_minerals = [minerals[i:i+5] for i in range(0, len(minerals), 5)]
    
    group_fatigue = []
    for group in grouped_minerals:
        fatigue_d = sum(1 for m in group)  # diamond
        fatigue_i = sum(5 if m == 'diamond' else 1 for m in group)  # iron
        fatigue_s = sum(25 if m == 'diamond' else 5 if m == 'iron' else 1 for m in group)  # stone
        group_fatigue.append((fatigue_d, fatigue_i, fatigue_s))
    
    group_fatigue.sort(key=lambda x: (x[2], x[1], x[0]), reverse=True)
    
    total_cost = 0
    print(group_fatigue)
    for fatigue in group_fatigue:
        if picks[0] > 0:  # diamond
            total_cost += fatigue[0]
            picks[0] -= 1
        elif picks[1] > 0:  # iron
            total_cost += fatigue[1]
            picks[1] -= 1
        elif picks[2] > 0:  # stone
            total_cost += fatigue[2]
            picks[2] -= 1
        else:
            break

    return total_cost

---

🗝️keypoint

1. 하나의 곡괭이가 5개의 연속적인 광물을 처리하기 때문에, 피로도가 높은 조합을 다이아몬드 곡괭이로 우선 처리한다.
2. 곡괭이가 모자란 경우(= 광물이 남는 경우), 처리하지 못하는 광물이 조합에 포함될 수 있기 때문에 사전에 이를 처리한다. (ex - [0,0,1], ['stone', 'stone', 'stone', 'stone', 'stone', 'diamond'])