[코딩테스트, C++, Softeer] 금고털이, 그리디 알고리즘

문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

 

코드

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

using namespace std;

int main(int argc, char** argv)
{
    int M,N;
    int answer = 0;
    vector<pair<int, int>> arr;
    cin >> M >> N;

    for (int i = 0; i < N; i++){
        int volume, price;
        cin >> volume >> price;
        arr.push_back(make_pair(price, volume));   
    }

    sort(arr.begin(), arr.end(), greater<>());

    for (int i = 0; i < N; i++){
        if (M >= arr[i].second){
            M -= arr[i].second;
            answer += arr[i].second * arr[i].first;
        }else if (M < arr[i].second && M > 0) {
            answer += M * arr[i].first;
            M = 0;
            break;
        }
    }
    cout << answer;
    return 0;
}

 

 

배워야할 점

1. sort, greater

먼저 vector을 정렬을 해야하는데 내림차순으로 정렬을 해야했다. 하지만 sort의 기본은 오름차순이기 때문에

greater<>()를 사용해서 내림차순으로 정렬할 수 있게 해야했다. 

greater를 사용할 때 <> 이렇게 타입을 안써어놨는데 C++14부터 추가된 타입추론에 의해서 생략을 해도 되는 것이다. 

 

2. pair, make_pair

pair는 짝을 이뤄줄 수 있게 해주는 class template이다. 그래서 여러 타입의 데이터들의 짝을 만들어 줄 수 있다.

예전에 42seoul 과제를 할 때, ford johnson 알고리즘에서 짝을 만들어줬을 때 사용해본 경험이 있었는데 다시 생각이 났다. 

 

애를 먹은 실수

for (int i = 0; i < N; i++){
        int volume, price;
        cin >> volume >> price;
        arr.push_back(make_pair(price, volume));
        sort(arr.begin(), arr.end(), greater<>());
}

 

 

아니 계속 답이 제대로 나오는데 테스트 2,4,5번이 시간 오류가 나는 것이었다. 어이없게도 내가 sort를 for문에 저렇게 넣어버려서 시간 에러가 났었다... 나 자신 정신차려.. ㅜㅜ