[프로그래머스] 광물 캐기 / 자바(Java)

문제

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

프로그래머스

 

---

해설

작업이 끝날때의 최소 피로도를 구하는 문제입니다.

광물을 순서대로 캐야하며, 광물의 순서에 규칙이 있는 것이 아니여서 완전탐색이 필요합니다. 또한 모든 가지수를 대입할 때 최대 광물의 수 50, 곡괭이는 각각 5개씩이므로 각 곡괭이의 선택 경우의수는 3의 10제곱정도라 시간, 공간 복잡도에 무리가 가지 않고 문제를 해결할 수 있습니다.

 

arr 이차원 배열을 통해 [곡괭이][광물] 인 경우의 피로도를 바로 얻을 수 있도록 하였습니다.

dfs를 통해 곡괭이의 남은 개수와 현재까지 채취한 광물의 수, 적용된 피로도를 넘기며 연산하다가 곡괭이를 모두 쓴 경우(pick_sum 이 0인 경우), 또는 모든 광물을 채취한 경우(index가 minerals의 개수만큼 된 경우)에 종료하여 각 시점의 피로도와 비교하는 형식으로 문제를 해결하였습니다.

---

코드

class Solution {
    int min = Integer.MAX_VALUE;
    int[][] arr = {
        {1,1,1},
        {5,1,1},
        {25,5,1}
    };
    int pick_sum;
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        pick_sum = picks[0]+picks[1]+picks[2];
        dfs(picks,minerals,0,0);
        answer = min;
        return answer;
    }
    int mineralsToInt(String mineral){
        if(mineral.equals("diamond")) return 0;
        else if(mineral.equals("iron"))return 1;
        else return 2;
    }
    public void dfs(int[] picks, String[] minerals, int minerals_index, int sum){
        if(pick_sum==0||minerals_index==minerals.length) {
            min = Math.min(min, sum);
            return;
        }
        // 다이아 곡괭이 사용
        if(picks[0]>0){
            picks[0]--;
            pick_sum--;
            int i=0;
            int add = 0;
            for(i=minerals_index;i<minerals_index+5;i++){
                if(i==minerals.length)break;
                add += arr[0][mineralsToInt(minerals[i])];
            }
            dfs(picks, minerals, i,sum+add);
            picks[0]++;
            pick_sum++;
            
        }
        // 철 곡괭이 사용
        if(picks[1]>0){
            picks[1]--;
            pick_sum--;
            int i=0;
            int add = 0;
            for(i=minerals_index;i<minerals_index+5;i++){
                if(i==minerals.length)break;
                add += arr[1][mineralsToInt(minerals[i])];
            }
            dfs(picks, minerals,i,sum+add);
            picks[1]++;
            pick_sum++;
            
        }
        // 돌 곡괭이 사용
        if(picks[2]>0){
            picks[2]--;
            pick_sum--;
            int i=0;
            int add = 0;
            for(i=minerals_index;i<minerals_index+5;i++){
                if(i==minerals.length)break;
                add += arr[2][mineralsToInt(minerals[i])];
            }
            dfs(picks, minerals, i,sum+add);
            picks[2]++;
            pick_sum++;
            
        }
    }
}