[프로그래머스 Level.2] 광물 캐기 (연습 문제) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 광물 캐기

 

 

 

문제 설명

 

 

 

마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

 

 

예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

 

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

 

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

 

즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.

 

마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

 

---

제한사항

• picks는 [dia, iron, stone]과 같은 구조로 이루어져 있습니다.
  • 0 ≤ dia, iron, stone ≤ 5
  • dia는 다이아몬드 곡괭이의 수를 의미합니다.
  • iron은 철 곡괭이의 수를 의미합니다.
  • stone은 돌 곡괭이의 수를 의미합니다.
  • 곡괭이는 최소 1개 이상 가지고 있습니다.
• 5 ≤ minerals의 길이 ≤ 50
  • minerals는 다음 3개의 문자열로 이루어져 있으며 각각의 의미는 다음과 같습니다.
  • diamond : 다이아몬드
  • iron : 철
  • stone : 돌

---

입출력 예picksmineralsresult

[1, 3, 2]	["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"]	12
[0, 1, 1]	["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]	50

---

입출력 예 설명

입출력 예 #1

다이아몬드 곡괭이로 앞에 다섯 광물을 캐고 철 곡괭이로 남은 다이아몬드, 철, 돌을 1개씩 캐면 12(1 + 1 + 1 + 1+ 1 + 5 + 1 + 1)의 피로도로 캘 수 있으며 이때가 최소값입니다.

입출력 예 #2

철 곡괭이로 다이아몬드 5개를 캐고 돌 곡괭이고 철 5개를 캐면 50의 피로도로 캘 수 있으며, 이때가 최소값입니다.

 

 

 

나의 코드

class Solution {
    int answer;
    int[] picks;
    String[] minerals;
    public int solution(int[] picks, String[] minerals) {
        this.answer = Integer.MAX_VALUE;
        this.picks = picks;
        this.minerals = minerals;
        
        for(int i=0; i<picks.length; i++) {
            if(picks[i] > 0) {
                picks[i]--;
                dfs(i, 0, 0);
                picks[i]++;
            }
        }
        
        return answer;
    }
    
    public void dfs(int pickType, int idx, int cost) {
        if(idx >= minerals.length) {
            answer = Math.min(answer, cost);
            return;
        }
        
        for(int i=idx; i<Math.min(idx + 5, minerals.length); i++) {
            if(pickType == 0) {
                cost++;
            } else if(pickType == 1) {
                if("diamond".equals(minerals[i])) {
                    cost += 5;
                } else {
                    cost++;
                }
            } else if(pickType == 2) {
                if("diamond".equals(minerals[i])) {
                    cost += 25;
                } else if("iron".equals(minerals[i])) {
                    cost += 5;
                } else {
                    cost++;
                }
            }
        }
        
        for(int i=0; i<picks.length; i++) {
            if(picks[i] > 0) {
                picks[i]--;
                dfs(i, idx + 5, cost);
                picks[i]++;
            }
        }
        
        for(int i=0; i<picks.length; i++) {
            if(picks[i] > 0) return;
        }
        
        answer = Math.min(answer, cost);
    }
}

 

풀이

1. 완전탐색 dfs를 이용하여 곡괭이를 사용하는 순서의 모든 경우로 광물을 캐며 곡괭이를 모두 사용했거나 광물을 모두 캤을 때 피로도를 구하여 최솟값을 answer에 저장하는 방식으로 풀었다.
2. 우선 answer를 int형 최댓값으로 초기화한다.
3. 주어진 picks를 순회하면서 해당 곡괭이가 있다면 해당 곡괭이를 하나 줄이고 해당 곡괭이로 dfs()를 진행한 후에 해당 곡괭이를 다시 하나 되돌린다.
4. dfs()에서는 우선 mineral의 인덱스를 나타낼 idx가 mineral의 인덱스를 넘어가면 해당 피로도(cost)를 answer와 비교하여 최솟값을 저장한다.
5. 아니라면 해당 idx부터 5개의 광물을 캐기 위해 idx + 5와 mineral의 길이를 비교하여 작은 값까지 순회하며 해당 곡괭이로 mineral을 캐는 경우의 피로도를 더해주도록 한다.
6. 그리고 다시 picks를 순회하면서 마찬가지로 해당 곡괭이가 있다면(0보다 크다면) 해당 곡괭이를 1 줄이고 idx를 5 증가시킨 후 해당 곡괭이로 dfs()를 재귀 호출한 후에 해당 곡괭이를 1 되돌린다.
7. 모든 곡괭이를 사용하였지만 광물이 남아있는 경우가 있기 때문에 picks를 다시 순회하여 모든 곡괭이가 0이라면 해당 피로도(cost)를 answer와 비교하여 최솟값을 저장해준다.
8. 이렇게 picks를 순회하며 곡괭이를 사용하는 순서의 모든 조합을 이용하여 해당 곡괭이로 광물을 캐며 피로도를 구한 후에 answer에 최솟값을 저장하였으므로 answer를 반환하면 된다.