Java 프로그래머스 광물 캐기

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

프로그래머스

문제 분류 : 코딩테스트 연습 > 연습문제 > 땅따먹기 

난이도 : 2

 

문제 접근

완전탐색 문제이다.

백트래킹을 통해서 사용 가능한 곡갱이로 광물을 캐고 피로도를 계산한다.

더이상 진행할 광물이 없거나 곡갱이를 모두 사용 했으면 전체 피로도를 min과 비교해서 min을 갱신한다.

정답 코드

import java.util.*;
class Solution {
    static int count; // 광물의 개수 
    static int answer;
    static int[] pick;
    static String[] mineral;
    public int solution(int[] picks, String[] minerals) {
        answer = Integer.MAX_VALUE;
        count = minerals.length; 
        pick = new int[picks.length];
        pick = Arrays.copyOf(picks, picks.length);
        mineral = new String[minerals.length]; 
        mineral = Arrays.copyOf(minerals, minerals.length);
        BackTracking(0, 0);
        return answer;
    }
    public static void BackTracking(int sum , int depth){
        int check = 0;
        for(int i = 0; i < 3; i++){
            check += pick[i];
        }
        if(depth == count || check == 0){
            answer = Math.min(answer, sum);    
            return;
        }
        for(int i = 0; i < 3; i++){
            if(pick[i] > 0){
                pick[i]--;
                int cnt = 0;
                int temp = 0;
                for(int j = depth; j < count; j++){
                    if(cnt == 5) break;
                    if(i == 0){
                        temp++;
                        cnt++;
                    }
                    else if(i == 1){
                        if(mineral[j].equals("diamond")){
                            temp += 5;
                        }
                        else{
                            temp++;
                        }
                        cnt++;
                    }
                    else{
                        if(mineral[j].equals("diamond")){
                            temp += 25;
                        }
                        else if(mineral[j].equals("iron")){
                            temp += 5;
                        }
                        else{
                            temp++;
                        }
                        cnt++;
                    }
                }
                BackTracking(sum + temp, depth + cnt);
                pick[i]++;
            }
        }
    }
}