[Programmers] 광물 캐기

광물 캐기

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

• 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

풀이1

처음에는 순열로 풀었다.
곡괭이는 최대 15개, 광물은 최대 50개 주어질 수 있어서 완전탐색이 가능하다고 판단
1. 각 순열의 결과마다 아래를 반복
2. 각 곡괭이는 광물을 5번 캘 수 있고 5번 캐기 전에 더 이상 캘 광물이 없으면 종료
3. 각 곡괭이마다 table(map) 이용하여 피로도 합산

코드

#include <bits/stdc++.h>
using namespace std;

int answer = INT32_MAX;
vector<int> tools;
unordered_map<string, int> table[3] = {
    {{"diamond", 1}, {"iron",1}, {"stone",1}},
    {{"diamond", 5}, {"iron",1}, {"stone",1}},
    {{"diamond", 25}, {"iron",5}, {"stone",1}},
};

int solution(vector<int> picks, vector<string> minerals) {
    // 곡괭이 번호 벡터(이미 정렬됨)
    for(int i=0; i<3; i++)
        while(picks[i]--)
            tools.push_back(i);
    
    do{
        int idx=0, res=0;
        bool flag=false;
        // 곡괭이 개수만큼 광물을 캐고 
        // 중간에 광물을 다 캐면 멈춤
        for(auto n : tools){
            // cout<<n<<' ';
            int count=5;
            while(count--){
                if(idx >= minerals.size()) {
                    flag=true;
                    break;
                }
                res += table[n][minerals[idx++]]; // 피로도 누적
            }
            if (flag) break;
        }
        // cout<<'\n';
        answer = min(answer, res);
        
    }while(next_permutation(tools.begin(), tools.end())); // 순열이용
    
    return answer;
}

풀이2

두번째는 만났을 때, 백트리킹으로 풀고 싶었다.
곡괭이는 최대 15개, 광물은 최대 50개 주어질 수 있어서 완전탐색이 가능하다고 판단
recur() 재귀 형태로 구현했고 base condition도 잘 했다. 또한, dia, iron, stone이 1개 이상이면 해당 곡괭이를 쓰며 광물이 남아있는 만큼 피로도를 합산했다.
하지만, 계속 실패했다. 그 원인은 각 곡괭이 피로도 누적에서 따로 변수를 취하지 않아 계속 이전 결과가 누적이 되었다. temp = 0을 추가해 해결

코드

#include <bits/stdc++.h>
using namespace std;

int answer = INT32_MAX;
int n;
void recur(vector<string>minerals, int dia,int iron,int stone,int idx,int res){
    if(dia+iron+stone==0 || idx>=n){
        answer = min(answer, res);
        return;
    }
    
    if(dia > 0){
        int temp = 0;
        for(int i=idx; i<idx+5; i++){
            if(i == n) break;
            temp++;
        }
        recur(minerals, dia-1, iron, stone, idx+5, res+temp);
    }
    if(iron > 0){
        int temp = 0;
        for(int i=idx; i<idx+5; i++){
            if(i == n) break;
            if(minerals[i]=="diamond") temp+=5;
            else temp++;
        }
        recur(minerals, dia, iron-1, stone, idx+5, res+temp);
    }
    if(stone > 0){
        int temp = 0;
        for(int i=idx; i<idx+5; i++){
            if(i == n) break;
            if(minerals[i]=="diamond") temp+=25;
            else if(minerals[i]=="iron") temp+=5;
            else temp++;
        }
        recur(minerals, dia, iron, stone-1, idx+5, res+temp);
    }
}

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

정리

순열을 이용한 풀이가 백트리킹을 이용한 풀이보다 시간이 더 오래 걸림.
backtracking에서 누적 계산할 때 조심하자!