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

문제

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

프로그래머스

 

풀이

문제를 잘 읽자 ! 처음에 아래 조건들을 하나같이 반대로 이해해서 잘못 구현했다.

 

사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다
.한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
광물은 주어진 순서대로만 캘 수 있습니다.
광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

 

완전 탐색으로 구현했다. 이유는 조건의 길이들이 길지가 않아 완탐으로 충분히 구현가능하기 때문이다.

풀이는 다음과 같다. 

1. 백트래킹으로 곡괭이들의 조합을 구한다.
2. 곡괭이 조합으로 모든 경우의 cost를 구해 minCost를 구한다.

 

 

코드

자바

import java.util.*;
import java.util.stream.*;
class Solution {
    //다이야0 철1 돌2 
    //곡괭이는 5번 사용하면 터짐
    HashMap<String, Integer> map ;
    int[][] cost;
    String[] minerals;
    int minLen;
    public int solution(int[] picks, String[] minerals) {
        map = new HashMap<>();
        int index = 0;
        this.minerals = minerals;
        minLen = Integer.MAX_VALUE;
        map.put("diamond", index++);
        map.put("iron", index++);
        map.put("stone",index++);
        cost = new int[][]{{1,1,1},{5,1,1},{25,5,1}};
        int pickLen = 0;
        for(int x : picks)pickLen+=x;
        
        dfs(new int[pickLen], 0, picks);
        
        return minLen;
    }
    public void dfs(int arr[], int L, int[] picks){
        if(L == arr.length){
            minLen = Math.min(minLen , getLen(arr));
            return;
        }
        for(int i= 0; i< picks.length; i++){
            if(picks[i]>0){
                picks[i]--;
                arr[L] = i;
                dfs(arr, L+1, picks);
                picks[i]++;
            }
        }
    }
    //곡괭이 종류info[], 곡괭이 개수 pick, map
    public int getLen(int[] arr){
        int ret = 0;
        int mIndex = 0;
        for(int x : arr){
            int cnt = 5;
            while(cnt-- > 0){
                if(mIndex == minerals.length)return ret;
                ret += cost[x][map.get(minerals[mIndex++])];
            }
        }
        return ret;
    }
}