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

문제

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

프로그래머스

 

문제 분석

 

곡괭이 리스트와 광물 리스트가 주어졌을 때 곡괭이 사용 순서를 잘 조절해서 피로도가 제일 적도록 해야한다.

곡괭이는 광물 5개를 캐고 나면 더이상 사용할 수 없다. 

곡괭이는 광물마다 캐는데 필요한 피로도가 다른데 해당 내용은 위의 표에서 확인할 수 있다.

 

문제 접근

 

우선 문제를 읽었을 때는 특정 규칙이 있을 수 있다는 생각이 들었지만 제한사항의 광물 리스트의 크기가 최대 50 이고 곡괭이도 종류 당 최대 5개 까지만 주어지기 때문에 완전 탐색을 해도 충분히 문제가 풀릴 수 있다 판단하였다.

 

dfs 를 사용하여 가능한 모든 방법을 탐색하면서 피로도를 계산해 더 적은 것으로  최신화 하였다.

모든 곡괭이를 다 사용하거나 모든 광물을 캤을 경우에는 탐색을 중지하였다.

 

 

코드

import java.util.Arrays;

class Solution {
    static int total;
    static int result = Integer.MAX_VALUE;
    
    public int solution(int[] picks, String[] minerals) {
        total = Arrays.stream(picks).sum();
        int[] visited = new int[picks.length];

        for (int i = 0; i < picks.length; i++) {
            if (visited[i] < picks[i]) {
                visited[i]++;
                dfs(i,1, 0, 0, picks, visited, minerals);
                visited[i]--;
            }
        }

        return result;
    }
    public static void dfs(int tool, int cnt, int mineralsIdx, int sum, int[] picks, int[] visited, String[] minerals){
        int r = 5;
        while (r > 0) {
            if (mineralsIdx >= minerals.length) {
                break;
            }

            if (tool == 0) { // 다이아몬드
                sum += 1;
            }else if(tool == 1){ // 철
                if(minerals[mineralsIdx].equals("diamond")) sum += 5;
                else sum += 1;
            }else{ // 돌
                if(minerals[mineralsIdx].equals("diamond")) sum += 25;
                else if(minerals[mineralsIdx].equals("iron")) sum += 5;
                else sum += 1;
            }

            mineralsIdx++;
            r--;
        }

        if (cnt == total || mineralsIdx == minerals.length) {
            result = Math.min(result, sum);
            return;
        }

        for (int i = 0; i < picks.length; i++) {
            if (visited[i] < picks[i]) {
                visited[i]++;
                dfs(i, cnt+1, mineralsIdx, sum, picks, visited, minerals);
                visited[i]--;
            }
        }
    }
}