Softeer 연습문제 2단계, 금고털이 그리디알고리즘 cpp풀이

 

 

오늘은 Softeer의 기초문제 중 하나인 금고털이 문제를 풀어보겠습니다.

금고털이 문제에 대한 자세한 내용 설명은 아래 링크를 참고 하시면 되겠습니다. 챙길 수 있는 무게 한도와 귀금속의 종류가 주어진 후, 귀금속 별 무게 및 무게당 가치가 주어졌을때, 챙겨갈 수 있는 최대 가치를 구하는 문제입니다. 여기에서 귀금속은 부분적으로 톱으로 잘라서 가져갈 수 있다는 점을 명심해야겠습니다.

무게당 가치가 높은 귀금속을 우선적으로 배낭에 챙겨서 최대가치의 귀금속을 챙길 수 있도록 해보겠습니다. 바로 cpp로 문제 풀어보겠습니다.

 

* Softeer 금고털이 문제설명 링크▼ 

Softeer

 

 

---

Softeer 2단계 연습문제, 금고털이 cpp 문제풀이

먼저 cpp 입출력, 벡터, 내장정렬함수 사용을 위한 헤더를 추가하고, 무게와 무게당 가치 정보를 담을 타입, Pair를 정의했습니다. 이후 각 귀금속 정보를 담을 1차원 벡터를 정의합니다.

 

 

 

 

배낭 무게와 귀금속 종류를 입력받고, 정답을 담을 변수 ans를 선언합니다. 
12 ~ 15행) 각 귀금속 별 무게와 무게당 가치를 입력받아 PV에 저장합니다.

 

 

 

17 ~ 19행) 먼저 담을 귀금속을 결정하기 위해 정렬을 진행합니다. PV의 귀금속 정보를 정렬하는데, 정렬 조건은 
1. 무게 당 가치가 더 큰 귀금속을 앞으로 정렬한다.
2. 무게 당 가치가 같다면, 무게 더 나가는 귀금속을 앞에 정렬한다.

두가지가 되겠습니다.

21 ~ 28행) 이후에 정렬된 귀금속을 하나하나 차례대로 배낭에 담습니다. 현재 보고 있는 귀금속이 배낭 한도 안으로 들어간다면, 전체 귀금속의 가치를 ans에 누적시킵니다. 만약 배낭에 해당 귀금속이 전부 들어가지 않는다면, 배낭에 딱 가득차는 만큼 톱으로 잘라내어 담고, 귀금속 가치를 ans에 누적시켜줍니다. 최종적으로 배낭에 담은 귀금속 가치 결과, ans를 출력하면 됩니다.

 

 

 

오늘은 이렇게 Softeer의 기초문제 중 하나인 금고털이를 풀어봤습니다. 그리디방식으로 조건에 맞는 귀금속을 정렬해서 배낭에 담음으로서 문제를 풀 수 있었습니다. 아래는 문제풀이 결과 및 전체 소스코드입니다. 질문 및 의견 언제든 댓글로 달아주세요. 이만 포스팅 마치도록 하겠습니다. 모두들 즐 코딩하세요.

 

 

---

Softeer 2단계문제, 금고털이 cpp 문제풀이 결과

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> Pair;
vector<Pair> PV;

int main() {
    int W, N; cin>>W>>N;
    int ans=0;
    for(int i=0; i<N; i++) {
        int M, P; cin>>M>>P;
        PV.push_back({M, P});
    }
    
    sort(PV.begin(), PV.end(), [](Pair &a, Pair &b) {
        return a.second > b.second || (a.second == b.second && a.first > b.first);
    });
    
    for(int i=0; i<PV.size(); i++) {
        if (W >= PV[i].first) {
            W -= PV[i].first;
            ans += PV[i].first * PV[i].second;
        } else {
            ans += W * PV[i].second;
            break;
        }
    }
    
    printf("%d\n", ans);
}