광물 캐기 (172927번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 광물 캐기 (172927번)

 

난이도 : Lv 2

알고리즘 : Dynamic Programming (동적계획법) & BFS (너비 우선 탐색)

 

 

def solution(picks, minerals):
    cost = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
    n = min(sum(picks), ((len(minerals)-1)//5)+1)
    mapping = {"diamond": 0, "iron": 1, "stone": 2}
    minerals = [mapping[i] for i in minerals]
    minerals = [[sum(cost[k][x] for x in minerals[i:i+5]) for k in range(3)] for i in range(0, n*5, 5)]
    q = {'000': 0}
    for i in range(n):
        tmp = {}
        for mask, fat in q.items():
            mask = list(map(int, mask))
            for k in range(3):
                if mask[k] == picks[k]:
                    continue
                mask[k] += 1
                cm = ''.join(map(str, mask))
                cf = fat + minerals[i][k]
                if cm in tmp:
                    tmp[cm] = min(tmp[cm], cf)
                else:
                    tmp[cm] = cf
                mask[k] -= 1
        q = tmp       
    return min(q.values())

 

 

bitmask dp 의 아이디어를 6진수로 확장시켜서 적용해봤다.

곡괭이의 각 광물마다 0~5 의 총 6가지 경우의 수가 있으므로, 6진수를 활용했다.

 

동적계획법 (DP) 를 적용시킬 수 있는 이유는 아래와 같다.

 

현재까지 stone과 dia, 2 개의 곡괭이를 사용했다고 가정하면

ⓐ dia → stone 을 사용한 경우

ⓑ stone → dia 를 사용한 경우

두 경우 모두 결국 stone 과 dia 곡괭이를 하나씩 사용한 것이다.

 

즉, 둘은 현재 같은 상태이다.

따라서 둘 중 피로도 값이 작은 것 하나만 남기고

앞으로의 계산에 활용하면 된다.

 

그렇기 때문에 이 문제에 DP를 적용할 수 있다.

 

---

 

아무 곡괭이도 사용하지 않은 '000' 상태에서,

BFS를 활용하여 곡괭이를 하나씩 사용하면서

최소의 피로도를 찾는 방식으로

코드를 구현했다.