백준 BOJ 16238 - 독수리

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

16238번: 독수리

왼쪽 / 오른쪽에서 접근한다는 함정에 안 속아넘어가도록 조심해야하는 문제.

 

얼핏보면 순서에 굉장한 제약을 받을 거 같지만,

실제로

 

원하는 값들을 꺼내고자 할때

꺼내고자 하는 값들이 미리 결정된다면

그 값을 꺼내기 위한 최적의 방법은 유일해진다.

값 두개를 순서대로 꺼낼 때

왼쪽에서 접근한다면 더 왼쪽에 있는 값을 먼저 꺼내야 함은 자명하고,

오른쪽에서 접근한다면 더 오른쪽에 있는 값을 먼저 꺼내야 함이 자명하다.

 

둘중 어떤것을 먼저 꺼내더라도

나머지 한개는 반드시 1만큼 줄어들기 때문에,

어떤 순서로 접근하던지 문제에서 요구하는 양의 최대 수는 변하지 않는다.

 

그러므로, 양을 최대한 많이 먹기 위해서는,

입력으로 들어오는 값들을 정렬한 후, 최댓값부터 먹기 시작하면 된다.

 

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

int cnt = 0;
int ans = 0;

priority_queue<int> pq;

int main(){
	int n,k;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> k;
		pq.push(k);
	}
	
	while(!pq.empty()){
		if(cnt >= pq.top()) break;
		
		ans -= cnt;
		cnt++;
		ans += pq.top(); pq.pop();
	}
	
	cout << ans;
	return 0;
}