[BOJ] 물건 팔기 1487번 C++

 

 

문제

세준이는 오랜 연구기간 끝에 신상품을 내놓았다. 세준이는 오랜 시간이 걸린 만큼 이 상품을 최대 이익에 팔려고 한다.

세준이는 이 상품을 사려고 하는 사람들이 총 몇 명이나 되는지 알아봤다. 무려 N명이나 살 의향을 보였다. 각각의 사람은 자기가 지불할 생각이 있는 최대 한도가 있다. 따라서, 어떤 사람이 20원까지 지불할 생각이 있는데, 세준이가 가격을 30원으로 책정하면 이 사람은 절대 안 살 것이고, 15원으로 책정하면 이 사람은 이 상품을 15원에 살 것이다. (단, 세준이가 안 팔수도 있다.)

그리고, 세준이는 각각의 사람에게 배달하는 비용이 얼마나 걸리는 지 알고 있다.

N명의 사람과, 각각의 사람이 지불할 용의가 있는 최대 금액과 배송비가 주어졌을 때, 세준이의 이익을 최대로 하는 가격을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 세준이의 물건을 구매할 의향이 있는 사람의 수 N이 주어진다. 이 값은 50보다 작거나 같다. 둘째 줄부터 각 사람이 지불할 최대 금액과 배송비가 공백을 사이에 두고 주어진다. 두 값은 모두 106보다 작거나 같은 음이 아닌 정수이고, 배송비는 0이 될 수도 있다.

출력

첫째 줄에 최대 이익을 만들어주는 가격을 출력한다. 이익이 최대인 가격이 여러개라면, 가장 낮은 가격을 출력한다. 또, 어떤 가격으로 팔아도 이익을 남길 수 없다면 0을 출력한다.

 

접근 방식

 

간단한 완전탐색 문제이다

구매할 사람들의 최대 금액을 모두 탐색하면서 어떤 값으로 판매했을 때 최대이익이 발생하는지 확인하면 된다.

 

이때, 주의할 점은

만약 지불할 최대 금액이 13 53 90일때

세준이가 13을 가격으로 설정하면 53으로 설정한 사람도 13으로 판매된다는 것이다.

 

또한, 가격보다 배달비가 비싸다면 세준이는 물건을 판매하지 않는다

 

이 두 가지만 유의한다면 간단하게 풀 수 있다.

 

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N; cin>>N;
    vector<pair<int,int>> p(N);
    set<int> maxCosts;
    for(int i=0; i<N; i++) {
        cin>>p[i].first>>p[i].second;
        maxCosts.insert(p[i].first);
    }

    int profit = 0, cost=0;

    int sum;
    for(auto mc : maxCosts) {
        sum = 0;
        for(int i=0; i<N; i++) {
            if(mc <= p[i].first) {
                if(mc - p[i].second > 0) {
                    sum += mc;
                    sum -= p[i].second;

                }
            }
        }

        if(sum > profit) {
            cost = mc;
            profit = sum;
        } 
    }
    cout<<cost;

    
    
}