백준 2786 상근이의 레스토랑

문제링크

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

문제

풀이

• 하나의 음식을 A로 내고나면 나머지는 전부 B로 내야 하기 때문에 먼저 B를 기준으로 오름차순으로 정렬을 한다음 0~(i-1) 음식의 B의 합을 계산해주었습니다.

• 이제 앞에서 더한 i개의 B중 하나를 버리고 A의 값으로 낼 음식을 정해야 합니다.
  이를 위해 두가지 경우로 나누었습니다.

1. 0~(i-1) 중에 A 값으로 계산할 음식을 정하는 경우

   a) 0~(i-1) 중에 A로낼 음식을 정한다면 B로내던 음식값을 A값이 대체하게 되므로 B-A가 가장 작은 음식을 A로 선택하면 됩니다.

2. i~(N-1) 중에 A 값으로 계산할 음식을 정하는 경우

   a) i~(N-1) 중에 A로 낼 음식을 정한다면 i~(N-1)중에 가장 저렴한 A를 선택하고 0~(i-1) 중 가장 비싼 (i-1)번째 B를 버리면 됩니다.

3. 1번 과 2번중 최솟값을 출력하였습니다.

• index를 증가시키며 같은 작업을 반복하였습니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 2000000001
vector<pair<ll, ll>> v;
ll minn[500001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fill(minn, minn + 500001, INF);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		v.push_back({ b,a });
	}
	sort(v.begin(), v.end());

	for (int i = v.size() - 1; i >= 0; i--) {
		minn[i] = min(minn[i + 1], v[i].second);// minn[i] = i~N 중 가장 저렴한 A값
	}

	ll diffidx, diff = -INF, sumn = 0;
	for (int i = 0; i < v.size(); i++) {
		sumn += v[i].first;
		if (v[i].first - v[i].second > diff) {
			diff = v[i].first - v[i].second;
			diffidx = i;
		}//최소의 B-A 를 가지는 index 저장
		if (i == 0) cout << minn[0] << '\n';
		else cout << min((v[diffidx].second + sumn - v[diffidx].first), (minn[i+1] + sumn - v[i].first)) << '\n';
	}
}

후기

쉬운듯 어려웠어요