2123번 : 인간 탑 쌓기

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

2123번: 인간 탑 쌓기

곡예사들의 위험도 중 가장 큰 값이 가장 작아지게 배치하는 문제이다.

아이디어 : 

주어진 곡예사들 중 가장 밑에 깔릴 하나를 구해야 한다는 느낌으로 접근한다.
모든 곡예사들에 대해 만약 그 곡예사가 가장 밑에 깔린다면 위험도는 얼마나 될지 구해본다.
구한 위험도 중 가장 작은 값을 갖고 있는 곡예사가 가장 밑에 깔린다.
밑에 깔린 곡예사는 이제 제외시키고 남은 곡예사들 중 가장 밑에 깔릴 곡예사를 선택한다.

하지만 이렇게 구현하게 되면 시간초과가 걸릴 것이다.
조금만 더 생각해보면 최초에 구한 위험도가 작은 순서대로 곡예사들이 선택되는 것을 알 수 있다.

따라서 N명의 곡예사들에 대해 각각 가장 밑에 깔릴 때 위험도를 기준으로 정렬해두고, 순서대로 탐색하며 위험도의 최대값을 구한다.

예를 들어보자. 문제의 예시처럼 (10,3), (2,5), (3,3) 이 입력으로 들어왔을 때,
(10,3) 곡예사가 가장 밑에 깔리면 위험도는 2가 될 것이다.
(2,5) 곡예사가 가장 밑에 깔리면 위험도는 8이 될 것이다.
(3,3) 곡예사가 가장 밑에 깔리면 위험도는 9가 될 것이다.
이 위험도를 기준으로 오름차순을 하면, 그 순서가 곧 밑에 깔리는 순서가 된다.

(10,3)을 밑에 깔고 나면 (2,5)와 (3,3)이 남는데, 둘의 위험도는 각각 방금 밑에 깔았던 (10,3)의 무게인 10을 빼준 값이다.
(2,5) 곡예사가 가장 밑에 깔리면 위험도는 -2가 될 것이다.
(3,3) 곡예사가 가장 밑에 깔리면 위험도는 -1이 될 것이다.

(2,5)를 밑에 깔고 나면 (3,3)이 남는데, 이 곡예사의 위험도는 방금 밑에 깔았던 (2,5)의 무게인 2를 빼준 값이다.
(3,3) 곡예사가 가장 밑에 깔리면 위험도는 -3이 될 것이다.

볼드 처리된 2, -2, -3 중 최대값은 2이므로 2가 정답이 된다.

구현 : 

먼저 {최초 위험도, 인덱스}를 저장하는 벡터를 선언하고, 여기에 각 곡예사마다 최초 위험도를 넣어준다.
최초 위험도는 (모든 곡예사들의 무게의 합)-(i번째 곡예사의 무게)-(i번째 곡예사의 버티는 힘)으로 구한다.

그 다음 최초 위험도를 기준으로 정렬 시켜놓고, (최초 위험도)-(밑에 깔린 곡예사들의 누적 무게)으로 위험도를 계산하여 최대값을 찾는다.

코드 : 

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
pii arr[50001];
vector<pii> v; // {위험도, 인덱스}
int main(){
	int N; cin>>N;
	int sum=0;
	for(int i=0; i<N; ++i){
		int a,b; cin>>a>>b;
		arr[i]={a,b};
		sum+=a;
	}
	for(int i=0; i<N; ++i){
		v.push_back({sum-arr[i].first-arr[i].second,i});
	}
	sort(v.begin(), v.end());
	int res=v[0].first;
	int acc=arr[v[0].second].first;
	for(int i=1; i<v.size(); ++i){
		res=max(res,v[i].first-acc);
		acc+=arr[v[i].second].first;
	}
	cout << res << '\n';
}