C++:: 프로그래머스 <광물 캐기>

dfs방식을 사용하면 편하게 접근할 수 있다. 곡괭이와 광물에 따른 값을 더해 나온 결과값들 중 최소값을 구하면 되는 문제이다. 크게 어렵지는 않지만 생각보다 까다롭다.

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

using namespace std;

int answer = INT32_MAX;

int cnt_tired(int cnt, int idx, vector<int> mine)
{
    int pick = (int)pow(5,2-idx), res = 0;
    // pick : 다이아 = 25, 철 = 5, 돌 = 1
    for(int i=cnt*5;i<(cnt+1)*5 && i<mine.size();i++)
    {
        int num = mine[i] / pick;//광물을 곡괭이값으로 나눈값이 표에있는값이다.
        if (num == 0) res++;// 곡괭이가 크면 0이기때문에
        else res += num;
    }
    return res;
}

void    dfs(int cnt, int res, vector<int> picks, vector<int> mine)
{
    if ((!picks[0] && !picks[1] && !picks[2]) || cnt*5 >= mine.size())// 곡괭이를 다 썻거나, 광물을 다 캤으면
    {
        answer = min(answer, res);// 최소값 저장
        return;
    }
    for(int i=0;i<3;i++)
    {
        if(picks[i])
        {
            picks[i]--;//곡괭이 개수--
            dfs(cnt+1, res+cnt_tired(cnt,i,mine), picks, mine);
            picks[i]++;//dfs넘겨주고 다시++
        }
    }
}
int solution(vector<int> picks, vector<string> minerals)
{
    vector<int> mine;
    for(auto c : minerals)
    {// 광물 : 다이아 = 25, 철 =5, 돌 =1 로 새로운 vector에 저장
        if(c[0]=='d') mine.push_back(25);
        else if(c[0]=='i') mine.push_back(5);
        else mine.push_back(1);
    }
    dfs(0, 0, picks, mine);
    return answer;
}

위 코드에서는 광물이 3가지 종류로 string의 0번째 값이 다 달라서 그냥 첫글자로 구분하여 사용하였지만 만약 광물의 이름이 정확히 일치해야하는 그러한 상황인 문제이면 strcmp함수를 사용하면된다.
string 은 strcmp에 바로 사용할 수 없으니 string s.c_str() 을 사용해 비교하면 된다.