[Programmers] Level 2 :: 광물 캐기 C++ 풀이

프로그래머스

먼저 나이브하게 문제를 접근해보자.
존재하는 곡괭이의 개수는 최대 15개이다. 그리고 광물의 개수는 50개이다. 곡괭이 무조건 5개의 광물을 캐야한다는 조건이 있다.

50개의 광물을 캐기 위해서는 10개의 곡괭이가 필요한 것을 알 수 있다. 즉, 최대 10개의 곡괭이만 사용하게 된다. 그러면 15개의 곡괭이 중 10개를 뽑는데 15C10의 시간복잡도가 소요된다. 그리고 뽑은 곡괭이를 최소값이 되도록 나열해야 하는데, 10!의 시간복잡도가 소요된다. 이 둘을 곱하면 절대 문제를 해결할 수 없다는 것을 알 수 있다.

어떻게 하면 효율적으로 모든 경우의 수를 찾을 수 있을까? 고민해봤다. 
가지치기로는 복잡도를 줄일 수 없다. 그래서 무조건 다이아 -> 철 -> 돌 곡괭이 순으로 선택을 진행하면 된다는 것을 알게 되었다.

좋은 곡괭이를 사용한다고 해서 손해볼게 없기 때문에 무조건 적으로 좋은 곡괭이를 선택해보자. 그러면 더이상 15C10의 시간복잡도 연산은 필요하지 않게 된다. 이미 내가 선택할 곡괭이는 결정되어 있으니..

따라서 시간복잡도 O(10!)에 문제를 해결할 수 있다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> v, b;
int E = 0, answer = 1e9;

void dfs(int s, int e, vector<string>&minerals) {
    if (s == e) {
        int idx = 0;
        int psum = 0;
        for (int i=0; i<minerals.size(); i++) {
            if (i % 5 == 0 && i != 0) {
                idx++;
            }
            if (idx == b.size()) break;
            
            int x = b[idx];
            string mineral = minerals[i];
            if (mineral == "diamond") {
                if (x == 0) psum++;
                if (x == 1) psum += 5;
                if (x == 2) psum += 25;
            }
            if (mineral == "iron") {
                if (x == 0) psum++;
                if (x == 1) psum++;
                if (x == 2) psum += 5;
            }
            if (mineral == "stone") {
                if (x == 0) psum++;
                if (x == 1) psum++;
                if (x == 2) psum++;
            }
            
        }
        answer = min(answer, psum);
        return;
    }
    for (int i=0; i<3; i++) {
        if (v[i] > 0) {
            v[i]--;
            b.push_back(i);
            dfs(s+1, e, minerals);
            b.pop_back();
            v[i]++;
        }
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    int m = minerals.size();
    v.push_back(0);
    v.push_back(0);
    v.push_back(0);
    for (int i=0; i<picks.size(); i++) {
        for (int j=0; j<picks[i]; j++) {
            if (m > 0) {
                E++;
                v[i]++;
                m -= 5;
            }
        }
    }
    dfs(0, E, minerals);
    return answer;
}