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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/172927

이 문제는 백트래킹을 이용하여 풀 수 있습니다. 주어진 minerals의 길이가 최대 50이고 곡괭이는 총 3종류, 그리고 하나의 곡괭이가 한번에 5개씩 캐기 때문에 최대의 경우를 백트래킹을 이용해서 탐색한다고 했을 때 시간 초과가 발생하지 않습니다. 따라서 하나의 곡괭이로 최대 5개의 광물을 연속으로 캔 뒤 곡괭이 수를 줄인 후 재귀 호출한 다음 곡괭이 수를 다시 늘린 상태로 현재 존재하는 곡괭이 수만큼 반복합니다.

여기서 주의할 점은 광물 캐기 피로도을 얻을 수 있는 경우를 잘 생각해야 하는 점입니다. 문제에서 광물 캐기 피로도를 얻을 수 있는 경우는 1. 모든 광물을 다 사용했을 때 2. 모든 곡괭이를 다 사용했을 때 입니다. 또한 곡괭이가 5개만을 캐는 것이 아니라 끝 지점에 도달하면 5개보다 적게 캐기 때문에 이 부분을 고려하여 범위를 설정해주시면 됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int answer = Integer.MAX_VALUE;
    
    public int solution(int[] picks, String[] minerals) {
        
        backtracking(picks,minerals,0,0);
        
        return answer;
    }
    
    static void backtracking(int[] picks, String[] minerals, int res, int idx){
        boolean allPicksUsed = true;
        for(int pick : picks){
            if(pick != 0){
                allPicksUsed = false;
                break;
            }
        }
        
        if(idx == minerals.length || allPicksUsed){
            answer = Math.min(answer,res);
            return;
        }
        
        for(int i=0;i<picks.length;i++){
            int newRes = res;
            if(picks[i]==0) continue;
            
            int fin = idx+5>minerals.length ? minerals.length : idx+5;
            for(int j=idx;j<fin;j++){
                switch(i){
                    case 0:
                        newRes++;
                        break;
                    case 1:
                        if(minerals[j].equals("diamond")) newRes += 5;
                        else newRes++;
                        break;
                    case 2:
                        if(minerals[j].equals("diamond")) newRes += 25;
                        else if(minerals[j].equals("iron")) newRes += 5;
                        else newRes++;
                        break;
                }
            }
            
            picks[i]--;
            backtracking(picks,minerals,newRes,fin);
            picks[i]++;
        }
    }
}