광물 캐기

광물 캐기

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

문제

풀이

1. 다이아몬드, 철, 돌의 피로도를 하나의 배열에 저장한다.
   
   조건에서 pick = [dia, iron, stone]이라고 명시하였으므로 위에 같이 피로도 배열을 정의한다.

2. DFS 백트래킹 방식으로 이 문제를 풀기 위해선 리턴(종료)조건을 정의한다.

• picks배열이 [0, 0, 0]일 경우(모든 곡괭이를 다 사용하였을 경우)
• minerals 포인터 ㅣ이 len(minerals) <= l일 때(모든 광물을 다 캤을 경우)
• 백트래킹 방식이므로 메모리제이션 기법을 사용(기존에 계산한 결과가 있을 경우)
  

3. 이제 발생할 수 있는 모든 경우를 코드로 나타낸다.
   

def solution(picks, minerals):
    tools = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]  ## 피로도 배열
    dp = {}  ## cache
    
    def dfs(l, picks):	##cache안에 있으면 리턴
        if (l, picks) in dp:
            return dp[(l, picks)]
        if l >= len(minerals):   ## 모든 minerals를 다 캤을 때
            return 0
        flg = True
        for i in range(len(picks)): ## 모든 곡괭이를 다 썻는지 확인
            if picks[i] != 0:
                flg = False
                break
        if flg:  ##모든 곡괭이 다 씀
            return 0
        picks = list(picks)
        num = float("inf")
        for i in range(len(picks)):
            if picks[i] == 0:  ## 해당 곡괭이는 더 이상 사용할 수 없음
                continue
            total, point = 0, 0 ## total은 총 피로도, point는 minerals의 포인터
            tmp = picks.copy()  
            tmp[i] = tmp[i] - 1  ## 해당 곡괭이를 사용했으므로 1을 빼준다.
            
            for j in range(l, l+5):  ## 연속으로 5개를 캐야하므로
                if j == len(minerals):  ## minerals 포인터가 minerals길이 보다 클경우 종료
                    break
                if minerals[j] == "diamond": ## 다이아일때 다이아 피로도 더해준다.
                    total += tools[i][0]
                elif minerals[j] == "iron": ## 철일때 철 피로도 더해준다.
                    total += tools[i][1]
                else:
                    total += tools[i][2] ## 돌일 때 돌 피로도 더해준다.
                point = j          ## 포인터를 업데이트 시켜준다.
            num = min(num, dfs(point + 1, tuple(tmp)) + total) ## 최소값을 구해야 하므로
        dp[(l, tuple(picks))] = num
        return num
        
    return dfs(0, tuple(picks))  ## 리스트는 해쉬가 안되므로 튜플로 변경
            

결과