[프로그래머스] Lv2. 광물 캐기

❓ 문제

⭕️ 풀이

가장 최소가 되는 값 구하기

1️⃣ 곡괭이의 순서 정하기
2️⃣ 곡괭이 하나당 5개의 광물 캐기
3️⃣ 곡괭이를 다 사용하거나 or 광물을 다 캐면 종료

가능한 모든 경우의 수를 따져보고 최소값을 구해야 하는 문제, 백트래킹 사용

✅ 곡괭이의 순서 정하기

✔️ 각 곡괭이는 사용 횟수가 정해져 있으므로 한 번씩 사용할 때마다 1씩 차감
✔️ 다 사용한 곡괭이는 0
✔️ 곡괭이의 값이 양수일 때만 사용

✅ 곡괭이 하나당 5개의 광물 캐기

✔️ minerals 배열이 5의 배수는 아니기 때문에 꼭 5개를 다 캐지 않게 될 수도 있다
✔️ 인덱스로 접근하면 인덱스 에러가 날 것 같아서 파이썬의 slice를 사용해 각 배열의 값에 직접 접근했다

✅ 곡괭이를 다 사용하거나 광물을 다 캐면 종료

모든 곡괭이(dia, iron, stone)의 합이 0이라면 더 이상 사용할 곡괭이가 없다
idx의 값이 minerals 배열을 넘어서면 모든 광물을 다 캔 것
이때 최소값을 비교한다

def solution(picks, minerals):
    answer = 1e9
    
    name = {
        "diamond": 0, "iron": 1, "stone":2
    }
    info = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
    
    # 다이아, 철, 돌 곡괭이, 캐야 하는 광물 인덱스, 피로도
    def mining(dia, iron, stone, idx, fatigue):
        nonlocal answer
        if idx >= len(minerals) or dia == iron == stone == 0:
            answer = min(answer, fatigue)
            print(fatigue)
            return 
        
        if dia:
            temp = 0
            for m in minerals[idx:idx+5]:
                temp += info[0][name[m]]
            mining(dia-1, iron, stone, idx+5, fatigue+temp)
        
        if iron:
            temp = 0
            for m in minerals[idx:idx+5]:
                temp += info[1][name[m]]
            mining(dia, iron-1, stone, idx+5, fatigue+temp)
        
        if stone:
            temp = 0
            for m in minerals[idx:idx+5]:
                temp += info[2][name[m]]
            mining(dia, iron, stone-1, idx+5, fatigue+temp)
    
    mining(*picks, 0, 0)
    return answer

유사문제

백준 이차원 배열과 연산