[C++] 광물 캐기 (프로그래머스 LEVEL 2)

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

프로그래머스

 

---

문제풀이

 

처음 생각 했던 방법은 dp를 사용한 풀이였다. 다이아 곡괭이를 사용했을 경우, 철 곡괭이를 사용했을 경우, 돌 곡괭이를 사용했을 경우를 각각 처리하여 피로도를 배열에 저장하는 방식이었다.

피로도[2][3] -> 0번 인덱스는 이전의 각 곡괭이 사용시 최소값이고, 1번 인덱스는 이전 각 곡괭이 사용시 최소값 + 현재 곡괭이 사용시 피로도이다. 그리고 각각 곡괭이 사용 가능 개수를 저장한다. 곡괭이[2][3][3] -> 0은 이전의 각 상황별 곡괭이고 1은 현재의 각 상황별 곡괭이이다.

말로 쉽게 풀어 써보려 했는데, 어렵다. 구현도 어렵다. 그래서 다른 방법을 생각했다.

 

5개 단위로 잘라 각 개수를 저장하는 것이다. 광물[n][3] 배열에 넣어 저장하면 된다. 이 때 주의할 점은 곡괭이를 모두 사용하면 그 이후의 광물은 캐지 않는 것이다. 그러므로 곡괭이 개수*5 보다 광물의 인덱스 값이 커지면 반복문을 중지하도록 하였다.

 

이렇게 나온 배열을 다이아, 철, 돌 순으로 정렬한 뒤 다이아 곡괭이, 철 곡괭이, 돌 곡괭이 순으로 소모하며 피로도를 계산하면 답이 나온다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

bool cmp(vector<int>& a, vector<int>& b) {
    if(a[0] > b[0]) return true;
    if(a[0] == b[0] && a[1] > b[1]) return true;
    if(a[0] == b[0] && a[1] == b[1] && a[2] > b[2]) return true;
    return false;
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    vector<vector<int>> v;
    vector<int> tmp(3, 0);
    int usable = (picks[0]+picks[1]+picks[2]) * 5;
    for(int i=0; i<minerals.size(); i++) {
    	// 곡괭이로 캘 수 있는 광물보다 많을 경우 중지
        if(i >= usable) break;
        
        if(minerals[i] == "diamond") tmp[0]++;
        if(minerals[i] == "iron") tmp[1]++;
        if(minerals[i] == "stone") tmp[2]++;
        
        // 5개 단위 혹은 마지막 광물까지 하나의 배열로 추가한다.
        if((i+1)%5 == 0 || i == minerals.size()-1) {
            v.push_back(tmp);
            tmp = {0, 0, 0};
        }
    }
    
    sort(v.begin(), v.end(), cmp);
    
    for(int i=0; i<v.size(); i++) {
        // cout << v[i][0] << " " << v[i][1] << " " << v[i][2] << endl;
        if(picks[0] > 0) {
            picks[0]--;
            answer += v[i][0] + v[i][1] + v[i][2];
        }
        else if(picks[1] > 0) {
            picks[1]--;
            answer += v[i][0]*5 + v[i][1] + v[i][2];
        }
        else {
            picks[2]--;
            answer += v[i][0]*25 + v[i][1]*5 + v[i][2];
        }
    }
    
    return answer;
}