https://school.programmers.co.kr/learn/courses/30/lessons/172927
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
최근 풀면서 가장 뭣같았던 문제였다.
접근 방법
처음에는 곡괭이를 통해 순열을 만들고 모든 경우를 비교하려고 했으나 시간초과가 예상되어, 그리디(Greedy) 알고리즘으로 접근했다.
핵심 아이디어는 다음과 같다:
- 광물을 5개씩 묶어서 각 구간의 "난이도"를 계산
- 난이도가 높은 구간부터 좋은 곡괭이를 배정
- 실제 캘 수 있는 구간만 처리 (곡괭이 개수 제한)
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;
}
정리
- 역시 그리디는 뭣같다.
- 좋은 곡괭이를 어려운 구간에 쓰는 것이 항상 최적이라는 걸 빠르게 알았어야 되었는데..
반응형
'PS' 카테고리의 다른 글
| [프로그래머스 Lv.2] 과제 진행하기 (0) | 2025.12.17 |
|---|---|
| [프로그래머스 Lv.2] 두 원 사이의 정수 쌍 (0) | 2025.12.16 |
| [프로그래머스 Lv.2] 연속된 부분 수열의 합 (0) | 2025.12.14 |
| [프로그래머스 Lv.2] 석유 시추 (0) | 2025.12.13 |
| [프로그래머스 Lv.2] 도넛과 막대 그래프 (0) | 2025.12.12 |