광물 캐기(24분)

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

구현 아이디어 4분 구현 20분

풀이

DFS를 이용한 완전 탐색 문제이다. 가능한 곡괭이의 조합을 전부 구하고 피로도를 계산했다.

#include <string>
#include <vector>

using namespace std;

// 다이아, 철, 돌
int axe[3], ch[10];
int mini = 2147000000;

void DFS(int L, int e, const vector<string>& minerals)
{
    if(L == e)
    {
        int N = minerals.size();
        
        int sum = 0;    // 피로도.
        int idx = 0;    // ch 배열 인덱스.
            
        for(int i = 0; i < N; i += 5)
        {
            int curaxe = ch[idx++];
            if(idx == e + 1) break;
            for(int j = i; j < i + 5 && j < N; ++j)
            {
                string curmineral = minerals[j];
                if(curaxe == 0) // 다이아 곡괭이.
                {
                    ++sum;
                }
                else if(curaxe == 1) // 철 곡괭이.
                {
                    if(curmineral == "diamond") sum+=5;
                    else ++sum;
                }
                else
                {
                    if(curmineral == "diamond") sum+=25;
                    else if(curmineral == "iron") sum+=5;
                    else ++sum;
                }
            }
        }
        
        // sum이 구해진 상태. mini와 비교 먼저.
        if(sum > mini) return;
        else mini = sum;
    }
    else
    {
        for(int i = 0; i < 3; ++i)
        {
            // 곡괭이가 남아 있다면.
            if(axe[i])
            {
                --axe[i];
                ch[L] = i;
                DFS(L + 1, e, minerals);
                ++axe[i];
            }
        }
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    
    int pickscnt = 0;
    for(int i = 0; i < picks.size(); ++i)
    {
        axe[i] = picks[i];
        pickscnt += picks[i];
    }
    
    int param = min(pickscnt, int((minerals.size() + 4) / 5));
    
    // 레벨, 광물을 다 캐기 위해 필요한 axe의 수.
    // 2번 테케 틀림: 위의 생각대로 풀었지만 필요한 axe 수보다 axe가 작을 수 있다.
    // 따라서 작은 값을 넣어주자.
    DFS(0, param, minerals);
    answer = mini;
    
    return answer;
}