프로그래머스 광물 캐기 [Lv. 2] (C++)

프로그래머스

다이아, 철, 돌 곡괭이의 개수를 입력으로 받을 때, 일을 마칠 수 있는 최소한의 피로도를 출력해주세요.

(곡괭이를 한번 선택하면 5개의 광물을 연속으로 캘 때 까지 다른 곡괭이는 사용할 수 없으며, 한번 사용한 곡괭이는 다시 사용할 수 없습니다.)

 

 

풀이 방법

DFS를 이용하여 모든 경우의 수를 순회하는 방법을 사용했습니다.

 

곡괭이는 각각 최대 5개씩, 총 15개를 가질 수 있습니다.

즉 경우의 수는 쉽게 생각해서 최대 3의 15승이라고 할 수 있겠으며, 시간 초과의 문제 없이 DFS로 풀이가 가능하겠습니다.

 

각 곡괭이 별로 재귀 로직을 만들어 주어 모든 경우의 수를 순회하면 되겠습니다.

 

void DFS(vector<string>& minerals, int dia, int iron, int stone, int cost = 0, int idx = 0)

저는 광석 정보를 담은 배열과 다이아, 철, 돌 곡괭이의 개수, 현재까지의 비용, 광석 index를 인자로 받는 함수를 작성 하였습니다.

 

int left = min(int(minerals.size()) - idx, 5);
if (dia > 0)
    DFS(minerals, dia-1, iron, stone, cost + left, idx + left);

각 곡괭이 별로 곡괭이의 개수와 비용, index를 업데이트하여 재귀 호출 하였습니다.

 

if (idx >= minerals.size() || dia + iron + stone == 0)
{
    answer = min(answer, cost);
    return;
}

 

모든 광석을 캔 상태이거나 모든 곡괭이를 사용했다면 answer를 업데이트 해주었습니다.

 

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

이후 DFS가 종료된 상태에서 최종 answer를 반환해주어 마무리합니다.

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer = 999999999;
void DFS(vector<string>& minerals, int dia, int iron, int stone, int cost = 0, int idx = 0)
{
	// 모든 광석을 캔 상태 || 모든 곡괭이 사용한 상태
    if (idx >= minerals.size() || dia + iron + stone == 0)
    {
        answer = min(answer, cost);
        return;
    }
    
    // min (남은 광석 수, 5개)
    int left = min(int(minerals.size()) - idx, 5);

    // 다이아몬드 곡괭이를 사용할 때
    if (dia > 0)
        DFS(minerals, dia-1, iron, stone, cost + left, idx + left);
    
    // 철 곡괭이를 사용할 때
    if (iron > 0)
    {
        int nxtCost = 0;
        for (int i = idx; i < idx + left; i++)
        {
            if (minerals[i] == "diamond")
                nxtCost+= 5;
            else 
                nxtCost += 1;
        }
        DFS(minerals, dia, iron-1, stone, cost + nxtCost, idx + left);
    }
    
    
    // 돌 곡괭이 사용할 때
    if (stone > 0)
    {
        int nxtCost = 0;
        for (int i = idx; i < idx + left; i++)
        {
            if (minerals[i] == "diamond")
                nxtCost += 25;
            else if (minerals[i] == "iron")
                nxtCost += 5;
            else 
                nxtCost += 1;
        }
        DFS(minerals, dia, iron, stone-1, cost + nxtCost, idx + left);
    }
    
}

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