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

 

프로그래머스

 

알고리즘 : DFS

언어: C++

 

INT_MAX를 정의했더니 프로그래머스에서 안먹혀서 일단 큰 수를 임의 작성함

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int answer = 99999999;
void dfs(vector<string> &m, int d, int ir, int s, int cost, int idx){

	// 개수가 적고, 곡괭이의 개수가 0일 경우 끝
    if (m.size() <= idx || d + ir + s == 0) {
        answer = min(answer, cost);
        return;
    }
    
    // 해당 곡괭이로 캘 수있는 광물의 수
    int goIdx = min(int(m.size())-idx, 5);
    
    // 다이아몬드 곡괭이는 cost가 1씩 증가하므로 idx와 동일하게 증가
    if (d > 0) {
        dfs(m, d-1, ir, s, cost + goIdx, idx + goIdx);
    }

    int goCost = 0;
    if (ir > 0) {
        for (int i = idx; i < idx + goIdx; i++) {
            if (m[i] == "diamond") {
                goCost += 5;
            } else {
                goCost += 1;
            }
        }
        dfs(m, d, ir-1, s, cost + goCost, idx + goIdx);
    }
    goCost = 0;
    if (s > 0) {
        for (int i = idx; i < idx + goIdx; i++) {
            if (m[i] == "diamond") {
                goCost += 25;
            } else if (m[i] == "iron") {
                goCost += 5;
            } else {
                goCost += 1;
            }
        }
        dfs(m, d, ir, s-1, cost + goCost, idx + goIdx);
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    dfs(minerals, picks[0], picks[1], picks[2], 0, 0);
    return answer;
}