이번 문제는 프로그래머스의 레벨 2 문제 광물 캐기이다.
이전에 풀었던 문제지만, 다시 보니 생각이 바로 나지 않았다.
그래서 다시 한 번 풀어보기로 다짐했다.
문제를 차근차근 한 번 읽어보도록 하자.
배열로 [dia, iron, stone] 순서의 곡괭이 정보가 주어진다.
각 곡괭이는 최대 5개까지 주어질 수 있다.
또한 1차원 배열로 캐야하는 광물의 정보가 주어지게 된다.
각 광물은 diamond, iron, stone으로 주어지며, 최대 50개가 주어진다.
이 때, 각 곡괭이로 캤을 때 누적되는 피로도가 서로 상이하며,
적절히 곡괭이를 사용하여 최소로 피로도를 사용하도록 해라!
단, 광물을 캐는 순서는 바뀔 수 없다.
완전탐색
처음 보았을 때, 곡괭이를 사용해서 모든 순서를 돌려볼 수 있을까? 싶었다.
최대 15개가 주어지고, 광물도 50개 밖에 되지 않기에 충분히 가능해보였다.
for문을 통해서 남은 곡괭이가 있으면, 선택하도록 한다.
이후 곡괭이를 모두 쓰거나 광물을 모두 캤으면 피로도를 갱신한다.
최종적으로 아래와 같이 백트래킹을 구현하였다.
int result = INF;
int calculate_fatigue(int pickaxe, int idx, vector<int> minerals_integer) {
// 넘어오는 매개변수는 곡괭이 종류, 현재 위치, 광물 배열
int fatigue = 0;
int pickaxe_coef = pow(5, 2 - pickaxe);
// 다이아 : 25, 철 : 5, 돌 : 1을 기준으로 나눔
for (int i = idx * 5; i < (idx + 1) * 5 && i < minerals_integer.size(); i++) {
int partial_fatigue = minerals_integer[i] / pickaxe_coef;
if (partial_fatigue == 0)
fatigue += 1; // 곡괭이가 더 세면 피로도 무조건 1
else
fatigue += partial_fatigue;
}
return fatigue;
}
void backtrack(int depth, int fatigue, vector<int>& picks, vector<int> minerals_integer){
if (!picks[0] && !picks[1] && !picks[2]) {
// 모든 곡괭이를 다 써버린 경우
result = min(result, fatigue);
return;
}
if (depth * 5 >= minerals_integer.size()) {
// 광물을 모두 다 캐서 더 이상 광물이 없는 경우
result = min(result, fatigue);
return;
}
for (int i = 0; i < 3; i++) {
// 여기서 곡괭이 종류를 선택한다.
if (picks[i]) {
picks[i]--;
backtrack(depth + 1, fatigue + calculate_fatigue(i, depth, minerals_integer), picks, minerals_integer);
picks[i]++;
}
}
}생각했던 대로, 크게 시간이 걸리지 않고 결과가 나왔다.
어차피 최대 50개의 광물까지 주어질 수 있으니,
곡괭이는 10개 까지 밖에 고를 수가 없는 문제이다.
그럼 모든 곡괭이가 남는다는 가정 하에 3^10 만큼 고를 수 있다.
시간초과가 전혀 발생할 수 없는 환경이라고 생각한다!
광물을 캐는 순서를 바꾸는 방법
또 다른 풀이로는, 광물을 캐는 순서를 바꾸는 방법이 있다.
바로 5개의 광물을 하나의 뭉치로 보는 것이다.
순서를 바꿀 수 없는 이유는, 하나의 곡괭이로 연속해서 캐야하기 때문이다.
하지만 5개까지만 연속해서 캐면 되기 때문에, 5개씩 묶는다면?
해당 뭉치들은 순서를 바꿔도 상관이 없게 된다!
그럼 이제 우리는 문제를 그리디하게 풀 수 있다!
어떻게 뭉치로 묶어서 저장할 수 있을까?
우선순위 큐를 이용하면 될 것 같다.
큐에 pair<vector, 피로도>를 저장을 하는 것이다.
이후 피로도가 높은 뭉치 우선, 광물의 수가 적은 뭉치 차선으로 정렬한다.
그럼 피로도가 높은 뭉치부터 다이아 곡괭이가 해결하면 될 것이다.
단, 주의할 점은 캘 수 있는 광물의 수이다.
예를 들어 광물의 수대로 모두 뭉치로 만들어버린다면?
곡괭이가 부족해 캘 수 없는 광물까지 캐버리게 된다.
따라서 min(max_pickaxe, mine_size)까지만 광물을 묶어야 한다!
최종적으로 아래와 같이 구현되었다.
struct cmp{
bool operator()(pvi a, pvi b) {
if (a.second == b.second)
return a.first.size() > b.first.size();
return a.second < b.second;
}
};
int result = 0;
priority_queue<pvi, vector<pvi>, cmp> mining_q;
void fill_queue(vector<int> picks, vector<string> minerals) {
int mine_size = minerals.size();
int max_mineral = (picks[0] + picks[1] + picks[2]) * 5;
// 최대로 캘 수 있는 미네랄은 곡괭이 수 * 5
for (int i = 0; i < min(max_mineral, mine_size); i += 5) {
// 최대로 캘 수 있는 미네랄 수 / 전체 미네랄 수
// 즉, 곡괭이를 다 쓰거나 전체 미네랄을 다 캘때까지 반복
int fatigue = 0;
vector<string> mine_vec;
for (int j = i; j < i + 5 && j < mine_size; j++) {
if (minerals[j] == "diamond")
fatigue += 25;
if (minerals[j] == "iron")
fatigue += 5;
if (minerals[j] == "stone")
fatigue += 1;
mine_vec.push_back(minerals[j]);
}
mining_q.push({ mine_vec, fatigue });
}
}
void calculate_fatigue(vector<int> &picks) {
while (!mining_q.empty()) {
if (picks[0]) {
for (int i = 0; i < mining_q.top().first.size(); i++)
result++;
picks[0]--;
}
else if (picks[1]) {
for (int i = 0; i < mining_q.top().first.size(); i++) {
if (mining_q.top().first[i] == "diamond")
result += 5;
else
result++;
}
picks[1]--;
}
else if (picks[2]) {
for (int i = 0; i < mining_q.top().first.size(); i++) {
if (mining_q.top().first[i] == "diamond")
result += 25;
else if (mining_q.top().first[i] == "iron")
result += 5;
else
result++;
}
picks[2]--;
}
mining_q.pop();
}
}