[Lv. 2] 광물캐기

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

프로그래머스

 

이 문제는 처음 접근 했을 때 곡괭이를 좋은 순서대로 사용하였다.

이유는 최소 피로도를 구하는 것이기 때문에 다이아 -> 철 -> 돌 곡괭이 순으로 광물을 캐면 최소 피로도가 나온다고 생각 하였다.

 

이 생각은 예시 상황에는 맞는 생각이였지만 철 -> 다이아 순으로 캘 때 최소가 되는 상황에서는 적합하지 않는 생각이였다.

또한 광물을 다 캤거나 곡괭이 수가 없을 경우도 사용할 수 없는 생각이였다.

따라서 다른 방법을 사용해야만 했다.

 

문제를 해결할 수 있는 알고리즘은 다음과 같다.

1. 곡괭이를 다이아, 철, 돌 중 하나를 선택하고 곡괭이 수를 감소시킨다.

2. 곡괭이를 사용해서 광물을 다섯번 캐고 피로도를 계산한다.

3. 다른 곡괭이를 사용해서 광물을 캔다.

4. 만약 곡괭이를 다 사용했거나 광물을 다 캔 경우 피로도를 갱신한다.

5. 다른 경우를 위해 사용한 곡괭이 수를 증가한다.

 

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
map<string, int> m; 
int fatigue[3][3] = {{1,1,1}, {5,1,1}, {25,5,1}}; 


void DFS(vector<int> &picks, vector<string> &minerals, int &answer, int sum, int location) {
    
    // 광물을 다 캤거나 곡괭이들을 다 썼을때 피로도를 갱신
    if(location==minerals.size() || (picks[0]==0 && picks[1]==0 && picks[2]==0)) {
        answer=min(answer,sum);
        return;
    }
    
    
    // 0~2 곡괭이 방문
    for(int i=0; i<3; i++) {
        
        // i곡괭이가 있다면
        if(picks[i]!=0) {
            picks[i]--;    
            
            int tmpIdx=location; // 캐야할 광물의 임시 인덱스.
            int tmpSum=sum; // 광물을 캐며 누적된 임시 피로도
            for(;tmpIdx<location+5 && tmpIdx<minerals.size();tmpIdx++) { // 5개를 캐거나 끝까지 캘때까지 
                tmpSum+=fatigue[i][m[minerals[tmpIdx]]]; // 광물의 번호
            }
            
            DFS(picks, minerals, answer, tmpSum, tmpIdx);
            
            picks[i]++;
        }
    }
    
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = (25*50)+1; // 최고 피로도*최대광물개수
    
    // "diamind" = 0, "iron" = 1, "stone" = 2
    m.insert({"diamond", 0});
    m.insert({"iron", 1});
    m.insert({"stone", 2});
    
    DFS(picks, minerals, answer, 0, 0);
    
    return answer;
}