[BOJ] 2786 - 상근이의 레스토랑

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

BOJ - 상근이의 레스토랑

문제 유형: 정렬, 그리디

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 256MB

 

문제

상근이는 도서관에서 번 돈으로 서강대 곤자가 플라자에 레스토랑을 하나 열었다. 이 레스토랑에는 음식을 N종류 팔고 있고, 손님은 서로 다른 음식을 여러개 시킬 수 있다. 이때, 음식을 시키는 순서가 중요하다. 그 이유는 각 음식을 첫 번째로 시킬 때의 가격과 아닐 때의 가격이 다르기 때문이다. 즉, 모든 음식 i의 가격은 첫 번째로 시킬 때의 가격 Ai와 아닐 때의 가격 Bi 두가지가 있다.

배가 고픈 창영이는 상근이네 레스토랑에서 음식을 시켜먹으려고 한다. 이때, 1개, 2개, ..., N개 시킬 때 필요한 최소 가격을 각각 구하는 프로그램을 작성하시오. 같은 종류 음식을 여러 번 중복해서 주문할 수 없다.

 

입력

첫째 줄에 상근이네 레스토랑의 음식의 개수 N(2 ≤ N ≤ 500,000)이 주어진다. 다음 N개의 줄에는 각 음식의 가격 Ai와 Bi가 주어진다. (0 ≤ Ai, Bi ≤ 1,000,000,000)

 

출력

출력은 총 N개로 이루어져 있다. i번째 줄에는 음식을 i개 시킬 때 필요한 최소 가격을 출력한다.

 

풀이

처음에는 유니온 파인드로 가장 작은 A를 관리하면서 그리디하게 풀었는데, 이는 방법이 아니였다.

 

풀이 참조:https://peisea0830.tistory.com/115

[Python 3] BOJ - 2786 "상근이의 레스토랑"

 

<A, B>그대로 배열에 담아서 B를 기준으로 오름차순 정렬한다.

suff_mins[i]에는 i ~ n-1까지의 최소값을 담을 것이다.

 

두 가지 케이스가 있기 때문이다:

1. 저렴한 B들 k-1개를 고르고 가장 싼 A 1개를 [k-1, n-1]범위 에서 구하기 - suff_mins를 이용하면 간단하게 구할 수 있다.

 

2. k개 그대로 구했다가, A로 바꿨을 때 가장 낮아지는 것을 구하기 - (A - B)를 담은 최소 힙의 꼭대기를 통해서 뭘 가장 먼저 주문하는게 이득인지 알 수 있다.

 

정답 배열에 매우 큰 값으로 초기화해준 다음, 1번케이스와 2번케이스별로 정답배열의 최소값을 갱신시키면 된다.

 

코드

C++

#include <bits/stdc++.h>

#include <climits>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

int n;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;

    vector<pii> arr;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        arr.emplace_back(a, b);
    }
    sort(arr.begin(), arr.end(), [](const auto &a, const auto &b) {
        if (a.second == b.second) return a.first < b.first;
        return a.second < b.second;
    });

    vector<int> suff_mins(n);
    suff_mins[n - 1] = arr[n - 1].first;
    for (int i = n - 2; i >= 0; i--) {
        suff_mins[i] = min(suff_mins[i + 1], arr[i].first);
    }

    ll sum = 0;
    vector<ll> ans(n, LLONG_MAX);
    for (int i = 0; i < n; i++) {
        ans[i] = min(ans[i], sum + suff_mins[i]);
        sum += arr[i].second;
    }

    priority_queue<int, vector<int>, greater<>> pq;
    sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i].second;
        pq.push(arr[i].first - arr[i].second);
        ans[i] = min(ans[i], sum + pq.top());
    }

    for (const auto &elem : ans) cout << elem << "\n";

    return 0;
}