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

프로그래머스

 

 

• 사용할 수 있는 곡괭이 중 하나를 임의로 선택
• 한 번 선택한 곡괭이는 광물 5개를 캘 때까지 사용
• 광물은 주어진 순서대로 채광 가능
• 모든 광물을 캐거나, 곡괭이를 전부 소모하면 종료
• 위 조건대로 채광 중 가장 피로도가 적게 소모된 경우의 피로도를 리턴

> 뭔가 이것 저것 복잡하게 생각했었는데 dfs로 모든 경우를 다 돌고 이 중 피로도의 최솟값을 리턴하면 되는 문제였다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// idx = 0: 다이아 = 25, 1: 철 = 5, 2: 돌 = 1
int cntFatigue(int cnt, int pickPower, vector<int> costs) {
    int res = 0;
    
    // 한 곡괭이를 5번 사용할 때 늘어나는 피로도
    for(int i = cnt * 5; i < (cnt + 1) * 5 && i < costs.size(); i++) {
        int cost = costs[i] / pickPower;
        
        // 곡괭이가 광물보다 강하면 피로도는 1씩 증가
        if(cost == 0) res++;
        else res += cost;
    }
    
    return res;
}

// cnt = 채광 사이클 횟수, res = 현재 피로도
void dfs(int cnt, int res, int& answer, vector<int> picks, vector<int> costs) {
    if((picks[0] == 0 && picks[1] == 0 && picks[2] == 0) || cnt * 5 >= costs.size()) {
        answer = min(answer, res);
        return;
    }
    
    // 세 종류의 곡괭이 사용
    for(int i = 0; i < 3; i++)
        // 해당 곡괭이가 0개가 아닐 때
        if(picks[i]) {
            // 개수 감소
            picks[i]--;
            // 사이클은 1, 피로도는 현재 피로도에서 cntFatigue(cnt, (int)pow(5,2 - i))만큼 증가
            dfs(cnt + 1, res + cntFatigue(cnt, (int)pow(5, 2 - i), costs), answer, picks, costs);
            // 다음 dfs에서 사용하기 위해 다시 값 증가
            picks[i]++;
        }
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 100000;
    
    vector<int> costs;
    
    // 각 광물에 해당하는 숫자를 costs 배열에 순서대로 삽입
    for(int i = 0; i < minerals.size(); i++) {
        if(minerals[i][0] == 'd') costs.push_back(25);
        else if(minerals[i][0] == 'i') costs.push_back(5);
        else costs.push_back(1);
    }
    
    // dfs 시작
    dfs(0, 0, answer, picks, costs);
    
    return answer;
}