백준 5911번 - 선물 (C++)

https://www.acmicpc.net/problem/5911

 

이 문제는 N이 1000이고 딱 하나의 물건만 할인할 수 있기 때문에 브루트포스 방식으로 모든 선물을 할인해볼 수 있다. 

그래서 N * N으로 해결할 수 있다.

 

먼저 모든 선물을 하나씩 할인해보고 그 이후 비용이 덜 드는 순서대로 정렬하고 가능할 때 까지 선물을 보내보면 된다.

 

그리고 만약 여기서 할인할 수 있는 선물이 여러개가 된다면

 

https://www.acmicpc.net/problem/25947

 

이 문제가 된다. 할인할 수 있는 선물이 한개가 아니기 때문에 N * N 으로풀 수 없는 여러개의 조합이 되어버려 브루트포스는 사용할 수 없고 이 문제에선 먼저 정렬을 통해 오름차로 만들고 이후 막혔을 때 할인을 계속 해보면서 정답을 찾아간다.

 

두 문제의 연결고리가 보여서 재밌는 문제였다.

 

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

using namespace std;

bool comp(pair<int, int>&a, pair<int, int>& b){
    return a.first + a.second < b.first + b.second;
}

int main(){
    int N, B; cin >> N >> B;

    vector<pair<int, int>> input;

    for(int i = 0; i < N; i++){
        int P, S;

        cin >> P >> S;

        input.push_back({P, S});
    } 

    int answer = 0;
    for(int i = 0; i < N; i++){
        vector<pair<int, int>> tmp = input;
    
        tmp[i].first /= 2;

        sort(tmp.begin(), tmp.end(), comp);

        int m = B;
        int cnt = 0;
        for(int j = 0; j < N; j++){
            m -= tmp[j].first + tmp[j].second;

            if(m >= 0){
                cnt++;
            }else{
                break;
            }
        }

        answer = max(answer, cnt);
    }

    cout << answer << '\n';
}