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

처음 문제를 보고 그리디일 것 같은데, 완전탐색이 속이 시원할거 같아서 완전탐색으로 풀어보았습니다.

로직에 틀린 부분이 없는거같은데, 100점이 나오시지 않는 분들은 아래의 반례로 테스트케이스 사용해 보시면 좋을것 같습니다.

 

["stone", "stone", "iron", "stone", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond"]
[1, 1, 0]
14

 

저도 처음에 100점이 안나와서 이 반례가 큰 도움이 되었습니다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//Greedy ? 
//BruteForce ?
//일단 문제해결 메커니즘의 아이디어 부터 떠올리고 -> 구현
// 현재 minerals의 idx와 누적 피로도 , 곡괭이 종류 매개변수를 통해 브루트포스
 
vector<int> FL;
 
void Search(int weapon, int fatigue, int idx, vector<int>& picks,vector<string>& minerals)
{
    int curFatigue = fatigue;
    picks[weapon]--;
    for (int i=0;i<5;i++)
    {
        if (idx > minerals.size()-1)
        {
            FL.push_back(curFatigue);
            return;
        }            
            
        string tmp = minerals[idx++];
        
        if (weapon == 0)
            curFatigue++;
        if (weapon == 1)
        {
            if (tmp == "diamond")
                curFatigue += 5;
            else
                curFatigue++;
        }
        if (weapon == 2)
        {
            if (tmp == "diamond")
                curFatigue += 25;
            else if (tmp == "iron")
                curFatigue += 5;
            else
                curFatigue++;
        }
    }
    
    if (picks[0] == 0 && picks[1] == 0 && picks[2] == 0)
    {
        FL.push_back(curFatigue);
        return;
    }
    
    if (picks[0] > 0)
    {
        Search(0,curFatigue,idx,picks,minerals);
        picks[0]++;
    }
    if (picks[1] > 0)
    {
        Search(1,curFatigue,idx,picks,minerals);
        picks[1]++;
    }
    if (picks[2] > 0)
    {
        Search(2,curFatigue,idx,picks,minerals);
        picks[2]++;
    }
        
}
 
 
int solution(vector<int> picks, vector<string> minerals) {
    
       
    for (int i=0;i<3;i++)
    {
        if (picks[i] > 0)
        {
            Search(i,0,0,picks,minerals);
            picks[i]++;
        }        
    }
    
    sort(FL.begin(),FL.end());
    return FL[0];
}