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

       문제 요약        

- 문제

 

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

 

         아이디어        

 

구현, dfs, 백트래킹

 

         소스코드        

 

import java.util.*;
class Solution {
    static int minCost = Integer.MAX_VALUE;
    static int N;
    static int[][] box = {{1,1,1},{5,1,1},{25,5,1}}; // 문제에서 나온 표를 정리해 둔다
    static Map<String, Integer> mineralTo; // diamond : 0, iron : 1, stone : 2 매핑한다
    static String[] mineral;
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        mineralTo = new HashMap<>();
        mineralTo.put("diamond", 0);
        mineralTo.put("iron", 1);
        mineralTo.put("stone", 2);
        mineral = minerals;
        
        N = minerals.length;
        back(0, picks, 0);
        return minCost;
    }

    static void back(int depth, int[] picks, int cost) {
        if(depth == N) {
            minCost = Math.min(cost, minCost);
            return;
        }
        int isAllUsed = picks[0] + picks[1] + picks[2];
        if(isAllUsed == 0) { // 모두 사용했다면, 
           back(Math.min(depth + 5, N) , picks, cost);
        }
        
        for(int i = 0; i < 3; i++) {
            if(picks[i] > 0) { // dia, iron, stone중에 하나 선택
                int nextCost = cost;
                for(int id = depth; id < Math.min(depth + 5, N); id++) {
                    int x = i;
                    int y = mineralTo.get(mineral[id]);
                    nextCost += box[x][y]; 
                }
                picks[i] -= 1; 
                back(Math.min(depth + 5, N) , picks, nextCost);
                picks[i] += 1; 
            }
            
        }
        
    }
}