Coding Test/programmers
[프로그래머스] 광물 캐기 c++
owls
2023. 10. 13. 23:38
728x90
문제 설명
제한 사항
- 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;
}
728x90