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

이 문제는 재귀를 이용해서 푸는 완전 탐색 문제이다.

 

이 문제에서 중요한 점은 하나의 곡괭이를 잡으면 광물 5개를 무조건 캐고 버린다는 것이다. minerals의 최대 길이가 50이고, 곡괭이는 3개 중 하나를 선택하게 되는데, 곡괭이 하나당 광물 5개를 캐므로 실제 최악 시간 복잡도는 3^10 ~= 60,000 이 되어 충분히 완전 탐색으로 문제를 풀 수 있다.

 

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

using namespace std;

#define DIA 0
#define IRON 1
#define STONE 2

#define INF 1000000000

int fatique(int pick, string mineral) {
    switch (pick) {
        case DIA:
            if (mineral == "diamond") {
                return 1;
            }
            else if (mineral == "iron") {
                return 1;
            }
            else {
                return 1;
            }
            break;
        case IRON:
            if (mineral == "diamond") {
                return 5;
            }
            else if (mineral == "iron") {
                return 1;
            }
            else {
                return 1;
            }
            break;
        case STONE:
            if (mineral == "diamond") {
                return 25;
            }
            else if (mineral == "iron") {
                return 5;
            }
            else {
                return 1;
            }
            break;
    }
    
    return -1;
}

int solve(vector<string>& minerals, int dia, int iron, int stone, int index) {
    if (index >= minerals.size()) {
        return 0;
    }
    
    if (dia == 0 && iron == 0 && stone == 0) {
        return 0;
    }
    
    int diaFat = INF;
    int ironFat = INF;
    int stoneFat = INF;
    // 1. dia
    if (dia > 0) {
        diaFat = 0;
        int i;
        for (i = index; i < index + 5; i++) {
            if (i >= minerals.size()) {
                continue;
            }
            
            diaFat += fatique(DIA, minerals[i]);
        }
        
        diaFat += solve(minerals, dia - 1, iron, stone, i);
    }
    
    // 2. iron
    if (iron > 0) {
        ironFat = 0;
        int i;
        for (i = index; i < index + 5; i++) {
            if (i >= minerals.size()) {
                continue;
            }
            
            ironFat += fatique(IRON, minerals[i]);
        }
        
        ironFat += solve(minerals, dia, iron - 1, stone, i);
    }
    
    // 3. stone
    if (stone > 0) {
        stoneFat = 0;
        int i;
        for (i = index; i < index + 5; i++) {
            if (i >= minerals.size()) {
                continue;
            }
            
            stoneFat += fatique(STONE, minerals[i]);
        }
        
        stoneFat += solve(minerals, dia, iron, stone - 1, i);
    }
    
    return min(diaFat, min(ironFat, stoneFat));
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    
    int dia = picks[0];
    int iron = picks[1];
    int stone = picks[2];
    
    answer = solve(minerals, dia, iron, stone, 0);
    
    return answer;
}