[C++] 백준/Silver/1487. 물건 팔기

문제: 물건 팔기 (백준 1487번)

문제 분석

문제 개요:

주어진 데이터는 각 물건의 가격과 그에 해당하는 판매 비용들이다. 문제의 목표는 특정 기준 가격 $p$를 정할 때 최대 이익을 주는 $p$의 값을 구하는 것이다. 단, 이익이 같은 경우 더 낮은 $p$를 선택해야 한다.

접근 방법:

1. 데이터 구조 선택:
   • 각 물건의 가격을 키로, 해당 가격에 해당하는 비용 리스트를 값으로 저장하기 위해 unordered_map<int, vector<int>>를 사용한다.
2. 이익 계산:
   • 모든 가격에 대해, 기준 가격 $p$를 정하고, 모든 물건들을 순회하면서 다음과 같이 이익을 계산한다:
     • 물건의 가격이 $p$ 이상이면 이익 없음
     • 물건의 가격이 $p$ 미만이면 $p - \text{물건 가격} - \text{판매 비용}$만큼의 이익 발생
3. 최적의 기준 가격 선택:
   • 계산된 이익의 합이 최대가 되는 기준 가격을 선택한다.
   • 최대 이익이 같은 경우, 더 작은 기준 가격을 선택한다.

---

코드 전체

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

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int n; 
    cin >> n;
    unordered_map<int, vector<int>> dict;
    // 물건의 가격과 해당 가격의 비용들을 dict에 저장
    for (int i = 0; i < n; i++)
    {
        int a, b; 
        cin >> a >> b;
        dict[a].push_back(b);
    }
    
    int maxVal = 0, answer = 0;
    // 모든 기준 가격 후보 i에 대해 이익 계산
    for (const auto &i : dict)
    {
        int sum = 0;
        // 모든 물건 가격 j에 대해 순회
        for (const auto &j : dict)
        {
            // j.second: j 가격에 해당하는 여러 비용들
            for (const auto &k : j.second)
            {
                // j.first: 실제 판매 가격, i.first: 기준 가격 후보
                // 기준 가격 이상인 경우 이익은 0, 미만인 경우 기준 가격에서 cost를 뺀 만큼 이익 발생
                if (j.first >= i.first && i.first - k > 0)
                    sum += i.first - k;
            }
        }
        // 최대 이익 갱신 및 기준 가격 선택 (같은 이익이면 더 낮은 기준 가격 선택)
        if (maxVal < sum)
        {
            answer = i.first;
            maxVal = sum;
        }
        else if (maxVal == sum)
        {
            if (answer > i.first)
                answer = i.first;
        }
    }
    cout << answer;
}