광물 캐기 - Lv2

 

문제

 

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

프로그래머스

 

 

 

풀이

 

재귀 + 제약조건을 사용하여 모든 경우의 수를 판단하였다.

이 과정에서 시간 낭비를 막기 위해 기저조건을 여러개 판단했다.

실제 풀이 과정에서 자꾸 에러가 나는 게 있었는데, 곡괭이를 사용하지 못하는 조건이 정산의 우선조건(모든 곡괭이 사용) 위에 있어서 났던 문제였다.

 

즉, 그냥 간단히 제약조건의 순서가 바뀌어서 에러가 났다는 이야기였다.

다음에는 이 부분을 조금 더 고려할 것.

 

또한, 코드에서 보완해야 할 점이 있다.

1. 피로도 계산 로직을 미리 HashMap 등으로 저장해놓고 반복해서 계산하는 것이 아닌 값을 호출할 것

2. 메모이제이션을 사용해서 반복 연산을 피할 것.

 

즉, 같은 배열의 광물 연속이라면 곡괭이와 배열 상태(ex : 2-1-1-1-2, 2-0-0-0-0)에 따른 피로도 소모를 저장한다면

계산 효율성을 높일 수 있을 것이다.

(단, 현재 문제에서는 경우의 수가 많지 않아 구현하지 않았다.)

 

코드

 

/*

picks = [dia, iron, stone] 순서, 각각 곡괭이의 개수를 의미, 각 곡괭이는 5개의 광물을 캐면 사용 불가
minerals = 광물의 순서
*/

import java.util.*;
class Solution {
    static int maxIdx;
    static int minRes = Integer.MAX_VALUE; //결과
    static int[][] chart = 
    {
        {1, 1, 1}, //다이아 곡괭이 - 다이아, 철, 돌
        {5, 1, 1}, //철 곡괭이 - 다이아, 철, 돌
        {25, 5, 1}, //돌 곡괭이 - 다이아, 철, 돌
    };
    public int solution(int[] picks, String[] minerals) {
        maxIdx = minerals.length - 1; //가능한 최대 인덱스
        
        solve(picks[0], picks[1], picks[2], minerals, 0, 0, 0); //다이아 곡괭이 사용
        solve(picks[0], picks[1], picks[2], minerals, 0, 0, 1); //철 곡괭이 사용
        solve(picks[0], picks[1], picks[2], minerals, 0, 0, 2); //돌 곡괭이 사용
        return minRes;
    }
    
    
    public void solve(int diaPix, int ironPix, int stonePix, String minerals[], int fatigue, int idx, int nowUse) {
        
        if(fatigue >= minRes) return; //최대 피로도 넘김
        if(diaPix == 0 && ironPix == 0 && stonePix == 0) { //모든 곡괭이 사용
            minRes = Math.min(minRes, fatigue); //정산
            return; 
        }
        if(nowUse == 0 && diaPix == 0 || nowUse == 1 && ironPix == 0 || nowUse == 2 && stonePix == 0) {
            return; //해당 곡괭이 사용 불가
        }


        //곡괭이 소모
        if(nowUse == 0) diaPix--;
        else if(nowUse == 1) ironPix--;
        else stonePix--;
        
        int count = 5; //한 곡괭이에 최대 5번 사용
        while(count-- > 0) {
            
            //광물 번호로 치환
            int mineralNum; 
            if(minerals[idx].equals("diamond")) mineralNum = 0;
            else if(minerals[idx].equals("iron")) mineralNum = 1;
            else mineralNum = 2;
            
            //자원 캐기(피로도 증가)
            fatigue += chart[nowUse][mineralNum];
            
            //인덱스 증가 및 전부 캤는지 확인
            idx++;
            if(idx > maxIdx) {
                minRes = Math.min(minRes, fatigue);
                return;
            }
        }

        //다음 재귀 시행
        solve(diaPix, ironPix, stonePix, minerals, fatigue, idx, 0);
        solve(diaPix, ironPix, stonePix, minerals, fatigue, idx, 1);
        solve(diaPix, ironPix, stonePix, minerals, fatigue, idx, 2);

        
    }
}