[프로그래머스 Lv.2] 광물 캐기

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

프로그래머스

 

최근 풀면서 가장 뭣같았던 문제였다. 

---

접근 방법

처음에는 곡괭이를 통해 순열을 만들고 모든 경우를 비교하려고 했으나 시간초과가 예상되어, 그리디(Greedy) 알고리즘으로 접근했다.

핵심 아이디어는 다음과 같다:

1. 광물을 5개씩 묶어서 각 구간의 "난이도"를 계산
2. 난이도가 높은 구간부터 좋은 곡괭이를 배정
3. 실제 캘 수 있는 구간만 처리 (곡괭이 개수 제한)

1. 구간별 난이도 계산

광물 5개씩 묶어서 각 구간의 가치를 계산했다. 이때 돌 곡괭이를 기준으로 피로도를 계산하여 난이도를 측정했다.

• diamond: 25점
• iron: 5점
• stone: 1점

int price(string s) {
    if (s == "diamond") return 25;
    else if (s == "iron") return 5;
    else return 1;
}

 

2. 캘 수 있는 광물 범위 제한

곡괭이 개수가 제한되어 있으므로, 실제로 캘 수 있는 광물 개수를 먼저 계산했다.

int total_picks = picks[0] + picks[1] + picks[2];
int idx = min((int)minerals.size(), total_picks * 5);

 

3. 구간 정렬

각 구간의 (난이도, 시작인덱스)를 pair로 저장하고, 난이도 기준 내림차순으로 정렬했다. 정렬 후에도 원래 광물 위치를 알기 위해 시작 인덱스를 함께 저장하는 것이 핵심이었다.

vector<pair<int, int>> prices;  // (난이도, 시작인덱스)
sort(prices.begin(), prices.end(), compare);

 

4. 곡괭이 배정 및 피로도 계산

정렬된 순서대로 순회하면서

• 난이도가 높은 구간부터 우선적으로 좋은 곡괭이(다이아 → 철 → 돌) 사용
• 각 구간의 시작 인덱스를 통해 실제 광물을 확인하고 피로도 계산
• 2차원 배열로 피로도 테이블을 만들어 코드를 간결하게 작성

int pro[3][3] = {
    {1, 1, 1},      // 다이아 곡괭이
    {5, 1, 1},      // 철 곡괭이
    {25, 5, 1}      // 돌 곡괭이
};

---

최종 코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int pro[3][3] = {
    {1, 1, 1},
    {5, 1, 1},
    {25, 5, 1}
};

bool compare(pair<int,int> a, pair<int,int> b) {
    return a.first > b.first;
}

int price(string s) {
    if (s == "diamond") {
        return 25;
    } else if (s == "iron") {
        return 5;
    } else {
        return 1;
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    
    int total_picks = picks[0] + picks[1] + picks[2];
    int idx = min((int)minerals.size(), total_picks * 5);
    
    vector<pair<int, int>> prices;
    
    for(int i=0;i<idx;i+=5) {
        int cnt = 0;
        if (i+5 < minerals.size()) 
        {
            for(int j=0;j<5;j++) {
                cnt += price(minerals[i+j]);
            }
        } 
        else 
        {
            for(int j=0;j<minerals.size() - i;j++) {
                cnt += price(minerals[i+j]);
            }
        }
        prices.push_back(make_pair(cnt, i));
    }
    
    sort(prices.begin(), prices.end(), compare);
    
    // 광질 ㄱㄱ
    for(int i=0;i<prices.size();i++) {
        // 일단 현재 광물 파악
        if (picks[0] > 0) {
            int start = prices[i].second;
            int idx = min((int)minerals.size(), start + 5);
            for(int j=start; j<idx; j++) {
                if (minerals[j] == "diamond") {
                    answer += pro[0][0];
                } else if (minerals[j] == "iron") {
                    answer += pro[0][1];
                } else {
                    answer += pro[0][2];
                }
            }
            picks[0]--;
        } else if (picks[1] > 0) {
            int start = prices[i].second;
            int idx = min((int)minerals.size(), start + 5);
            for(int j=start; j<idx; j++) {
                if (minerals[j] == "diamond") {
                    answer += pro[1][0];
                } else if (minerals[j] == "iron") {
                    answer += pro[1][1];
                } else {
                    answer += pro[1][2];
                }
            }
            picks[1]--;
        } else {
            int start = prices[i].second;
            int idx = min((int)minerals.size(), start + 5);
            for(int j=start; j<idx; j++) {
                if (minerals[j] == "diamond") {
                    answer += pro[2][0];
                } else if (minerals[j] == "iron") {
                    answer += pro[2][1];
                } else {
                    answer += pro[2][2];
                }
            }
            picks[2]--;
        }
    }

    
    return answer;
}

정리

• 역시 그리디는 뭣같다.
• 좋은 곡괭이를 어려운 구간에 쓰는 것이 항상 최적이라는 걸 빠르게 알았어야 되었는데..