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

문제 설명

문제 바로가기

 

제한 사항

• picks는 [dia, iron, stone]과 같은 구조로 이루어져 있습니다.
  • 0 ≤ dia, iron, stone ≤ 5
  • dia는 다이아몬드 곡괭이의 수를 의미합니다.
  • iron은 철 곡괭이의 수를 의미합니다.
  • stone은 돌 곡괭이의 수를 의미합니다.
  • 곡괭이는 최소 1개 이상 가지고 있습니다.
• 5 ≤ minerals의 길이 ≤ 50
  • minerals는 다음 3개의 문자열로 이루어져 있으며 각각의 의미는 다음과 같습니다.
  • diamond : 다이아몬드
  • iron : 철
  • stone : 돌

입출력 예

picks	minerals	result
[1, 3, 2]	["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"]	12
[0, 1, 1]	["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]	50

풀이

곡갱이를 선택해서 피로도를 최솟값으로 만들어야 하는 문제입니다.

 

처음에는 picks에서 다이아몬드부터 선택해서 하면 최솟값이 되겠지라고 생각했는데 아니였습니다.

minerals에서 5개씩 나누고 해당 광물 집합에 따라 곡갱이를 선택해야합니다.

 

dfs로 최솟값을 찾는 문제입니다.

 

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

using namespace std;

int len = 0, answer = INT16_MAX;
unordered_map<string, int> mineral, hash;
vector<vector<int>> board;
vector<string> vec;

void dfs(vector<int> &picks, int location, int sum){
    int sumList[3] = {0,};
    int point = 0;
    if(len <= location || picks[0] + picks[1] + picks[2] == 0 ){
    //끝까지 가거나 곡괭이를 다 쓸 경우
        answer = min(answer, sum);
        return;
    }
    for(int i = location; i < location + 5; i++){
        if( i >= len){
            point = i;
            break;
        }
        //각 곡괭이별로 피로도 계산
        sumList[0] += board[0][mineral[vec[i]]];
        sumList[1] += board[1][mineral[vec[i]]];
        sumList[2] += board[2][mineral[vec[i]]];
        point = i;
    }
    for(int i = 0; i < 3; i++){
        if(picks[i] != 0){
            picks[i] -= 1;
            dfs(picks, point+1, sum+sumList[i]);
            picks[i] += 1;
        }
    }
}

int solution(vector<int> picks, vector<string> minerals) {
       
    board = {
        {1,1,1}, {5,1,1}, {25, 5, 1}
    };
    vec = minerals;
    mineral["diamond"] = 0;
    mineral["iron"] = 1;
    mineral["stone"] = 2;
    
    len = minerals.size();
    
    dfs(picks, 0, 0);
    
    return answer;
}