백준 16238 독수리

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

16238번: 독수리

그리디 문제였습니다.

배열에서 한칸에 있는 양을 먹을때마다 전체 배열에 있는 양이 1씩 줄어들며 지나온 칸에 있는양이 없어지는데 직관적으로 순서와 상관없이 먹을 칸을 정할 수 있다는걸 알 수 있습니다. 

예를 들어 배열에 1 5 1 10 1 11 1 이라 했을때 지나온 칸들의 양은 없어지므로 5 10 11만 택해서 먹을 수 있는것입니다. 

따라서 우리가 t시간동안 양을 먹는다 할때 먹는 양을 최대화하려면 당연하게도 가장 양이 많이 들어있는 칸들 t개만 먹게 될것입니다. 이제 답이될수있는 t를 정하면되는데  어떤 칸의 양이 t보다 작게된다면 먹을 필요가 없으므로 내림차순으로 순차적으로 양을 먹었을때 현재 t보다 양이 작아지기전까지 먹으면됩니다.

저는 우선순위 큐를 통해 풀었습니다.

#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int main(){
    fast_io();
    int N;
    cin>>N;
    priority_queue<int> pq;
    for(int x=0;x<N;x++){
        int input;
        cin>>input;
        pq.push(input);
    }
    int solve=0;
    for(int x=0;x<N;x++){
        if(pq.top()>x){
            solve+=pq.top()-x;
        }
        else break;
        pq.pop();
    }
    cout<<solve;
}