프로그래머스 [Lv. 2] 광물 캐기 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

정답 코드

answer = 1251
def solution(picks, minerals):
    fatigue = {
        0: [1, 1, 1],
        1: [5, 1, 1],
        2: [25, 5, 1]
    }
    dictM = {
        "diamond": 0,
        "iron": 1,
        "stone": 2,
    }
    lenM = len(minerals)
    last = lenM // 5 + 1
    
    def dfs(s, tot):
        if s == last or sum(picks) == 0:
            global answer
            if answer > tot:
                answer = tot
            return
        for d in range(3):
            if picks[d]:
                picks[d] -= 1
                newTot = tot
                for i in range(s*5, min(s*5+5, lenM)):
                    m = dictM[minerals[i]]
                    newTot += fatigue[d][m]
                dfs(s+1, newTot)
                picks[d] += 1
    dfs(0, 0)
    return answer

풀이 방법

1. 광물에 따른 피로도를 딕셔너리로 만든다.
2. 해당 광물이 몇 번째 인덱스인지 표시해주는 딕셔너리를 만든다.
3. dfs를 실행한다.
   1. 종료 조건
      1. 곡괭이가 없는 경우 = sum(picks) = 0 또는 s가 last인 경우
         1. last는 미네랄의 총 개수를 5로 나눈 몫에 + 1을 한 값이다.
      2. 종료 조건을 만족하는 경우 글로벌 answer를 가져와서 최소값으로 교체한다.
         1. answer값이 1251인 이유 minerals의 범위 50에 최대 피로도 25를 곱하고 혹시 몰라서 1을 더해줬다.
   2. 광물이 3개 이므로 범위는 3
      1. picks에 d번째 인덱스의 값이 있을 때 = 곡괭이가 존재할 때
         1. 미리 만들어둔 fatigue와 dictM을 사용해서 newTot 값을 만든다.
         2. dfs(s+1, newTot)로 재귀 함수를 실행한다.
4. answer를 출력한다.

느낀점

• 다행이도 오래 걸리지 않은 문제