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

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int answer=1500;
void recur(int t,int d,int i,int s,int size,vector<string>& minerals)
{
    if(size==minerals.size()||(d==0&&i==0&&s==0))
    {
        if(answer>t)answer=t;
        return;
    }
    int ct=0,curSize = (size+5>minerals.size())?minerals.size()-size:5;
    if(d>0)
    {
        for(int j=size;j<size+curSize;j++)
        {
            ct++;
        }
        recur(t+ct,d-1,i,s,size+curSize,minerals);
    }
    if(i>0)
    {
        ct=0;
        for(int j=size;j<size+curSize;j++)
        {
            if(minerals[j]=="diamond")ct+=5;
            else ct++;
        }
        recur(t+ct,d,i-1,s,size+curSize,minerals);
    }
    if(s>0)
    {
        ct=0;
        for(int j=size;j<size+curSize;j++)
        {
            if(minerals[j]=="diamond")ct+=25;
            else if(minerals[j]=="iron")ct+=5;
            else ct++;
        }
        recur(t+ct,d,i,s-1,size+curSize,minerals);
    }
}

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

 

주어진 곡괭이들과 광석배열을 이용해 가장 적은 피로도로 채광했을 때의 피로도를 구하는 문제이다. 

간단하게 dfs를 이용해 완전탐색방식으로 구현했다. 

 

광석을 다 캤거나 곡괭이를 다 썼다면 종료한다. 

if(size==minerals.size()||(d==0&&i==0&&s==0))
    {
        if(answer>t)answer=t;
        return;
    }

이 때, 최소값을 갱신한다. 

 

int ct=0,curSize = (size+5>minerals.size())?minerals.size()-size:5;
    if(d>0)
    {
        for(int j=size;j<size+curSize;j++)
        {
            ct++;
        }
        recur(t+ct,d-1,i,s,size+curSize,minerals);
    }
    if(i>0)
    {
        ct=0;
        for(int j=size;j<size+curSize;j++)
        {
            if(minerals[j]=="diamond")ct+=5;
            else ct++;
        }
        recur(t+ct,d,i-1,s,size+curSize,minerals);
    }
    if(s>0)
    {
        ct=0;
        for(int j=size;j<size+curSize;j++)
        {
            if(minerals[j]=="diamond")ct+=25;
            else if(minerals[j]=="iron")ct+=5;
            else ct++;
        }
        recur(t+ct,d,i,s-1,size+curSize,minerals);
    }

끝나지 않았다면 ct 현재 피로도와 curSize 이번에 몇개를 캘 수 있는지를 초기화한다. 

그 후, if문을 통해 곡괭이가 있다면 다이아,철, 돌 곡괭이 순으로 사용하고 재귀호출을 한다. 

즉 한번의 함수호출에서 곡괭이 1개를 소모하는 것이다. 

 

이렇게 가장 적은 피로도의 경우의 수를 찾을 수 있다.