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

❓문제설명

광물캐기

프로그래머스

---

🔍 문제해석

어떤걸 풀어야 할까?

• 곡괭이로 광물을 캐면 피로도가 쌓인다. 광물을 다 캤을때 가장 적게 쌓일 수 있는 피로도를 구하자
• 곡괭이는 3개의 종류가 존재하고 곡괭이마다 광물을 캐는데에 쌓이는 피로도가 다르다.
• 한개의 곡괭이는 5번의 광물캐기를 하면 소멸되면서 더이상 사용 할 수 없다.

---

🧐 문제 풀이

• 풀이 전략 구상

참고 블로그 : https://kjk04021.tistory.com/124

 

각 곡괭이들이 각각 광물을 캐는 모든 경우의 수를 보아야하기 때문에 재귀로 생각하였다. 

 

돌 < 철 < 다이아 순서대로 강하며, 약한 곡괭이가 그 보다 강한 광물을 캘때 피로도는 5의 제곱이 되고

강한 곡괭이가 그보다 약한 광물을 캐거나 동급이라면 1이다.

예를 들어, 돌 곡괭이가 철을 캐면 철이 돌보다 1단계 강하므로 피로도는 5의 1제곱, 5이다.

근데 만약 돌 곡괭이가 다이아몬드를 캐면 다이아가 돌보다 2단계 강하니까 피로도는 5의 2제곱, 25가 된다.

 

구상하기 어려웠던건 현재 캐는 광물의 위치이다.

하나의 배열을 재귀함수에서 계속 참조하면서 원소를 빼거나 배열을 자르지 않고, 계산하는 위치를 구할 것 인가...

답은 재귀함수 호출시 현재 광물의 index를 같이 넘기는 것이었다.

그래서 minerals[index + 곡괭이 시도 횟수]로 캐고자하는 광물을 알 수 있었다. 

 

• 알고리즘 선택

모든 경우의 완전 탐색을 위해 DFS 사용.

---

！ 제출코드

1. 곡괭이와 광물의 강함 정도 계산을 위해 곡괭이의 순서와 똑같이 광물의 순서를 담은 리스트 생성
2. 탐색을 위한 dfs 함수 호출, 광물의 현재위치나 피로도의 합산은 0을 준다.
3. 사용할 수 있는 곡괭이가 없다면 answer와 현재의 피로도를 비교하여 더 적은 값을 answer로 대입한다.
4. 사용가능한 곡괭이가 있다면 5번의 시도를 통해 광물을 캔다.
5. 아직 캘 광물이 남아 있다면 피로도 계산을 하고 그 값을 res에 합산한다.
6. 없다면 answer와 현재의 피로도를 비교하여 더 적은 값을 answer로 대입한다.
7. 광물캐기가 끝나면 해당인덱스의 곡괭이를 하나 빼준다.
8. 다음 단계를 위해 dfs를 호출하는데, 광물을 다섯개캤으니 광물의 현재위치는 +5를 해준다.
9. 다른 케이스를 위해 빼줬던 곡괭이의 개수를 원복시킨다.

import java.util.*;

class Solution {

    // (1)
    static ArrayList<String> tiredness = new ArrayList<>(Arrays.asList("diamond", "iron", "stone"));
    static int answer = Integer.MAX_VALUE;
    
    public  int solution(int[] picks, String[] minerals) {
       // (2)
        DFS(picks, minerals, 0, 0);
        return answer;

    }
    public void DFS(int[] picks, String[] minerals, int idx, int result) {
        
        int mineralLength = minerals.length;
        int re = 0;
            
        // (3) 사용할 수 있는 곡괭이가 없을 때
        if (picks[0] == 0 && picks[1] == 0 && picks[2] == 0) {
        
            answer = Math.min(answer, result);
            return;
        }
        
        // 3개의 곡괭이 중에 1개 선택
        for (int i = 0; i < 3; i++) {
        
            re = result;
            
            if (picks[i] > 0) {
            
                // (4) 1개의 곡괭이가 광물 5개 캘 수 있다.
                for (int j = 0; j < 5; j++) {
                
                    // (5) 캘 광물이 아직 남아있다면
                    if (idx + j < mineralLength) {
                     
                        int findMineralIdx = tiredness.indexOf(minerals[idx + j]);
                        if (i > findMineralIdx) re += Math.pow(5, i - findMineralIdx);
                        else re++;
                        
                    } else {
                    
                        // (6)광물을 다 캤다면
                        answer = Math.min(answer, re);
                        return;
                    }
                }
                
                // (7)사용한 광물을 빼주고 dfs 실행
                picks[i]--;
                // (8)
                DFS(picks, minerals, idx + 5, re);
                // (9)다른 케이스를 위해 원복
                picks[i]++;
            }

        }
    }
}