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

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

 

처음에는 다이아 - 철 - 돌 순이여서 그냥 순회하면서 캐면 되는 건줄 알았는데

곡괭이마다 다른 광석에 대한 피로도 계산을 해줘야 하기때문에 DFS로 하는게 맞다고 한다. 

DFS를 통해 좋은 곡괭이로 캘 수 있는 모든 광석을 캐주고 다음 곡괭이로 넘어가면 된다.

#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}}; // [곡괭이로][해당 광물 캘 때] = 드는 피로도
//하나의 곡괭이로 계속해서 캐야함 => DFS
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; // 최고 피로도 * 최대 광물 개수
    
    m.insert({"diamond", 0});
    m.insert({"iron", 1});
    m.insert({"stone", 2});
    
    DFS(picks, minerals, answer, 0, 0);
    
    return answer;
}