백준 26123번: 외계 침략자 윤이 (C++)

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

26123번: 외계 침략자 윤이

---

Level: Silver IV

Solved By: Priority Queue, Prefix Sum

 

h값들을 받으면서 MaxHeap(Priority Queue)에 넣어줬습니다. 이유는 레이저를 쏘며 높이를 깎아가는 데에 있어 h-1이 다음 레이저를 쏠 때 높이이기 때문에 높이를 깎는 과정에서도 다음 높이(다음 최댓값)를 알기 위해 우선순위 큐를 사용했습니다. 즉, 우선순위 큐는 현재 깎아야 할 높이가 무엇인가를 알기 위한 용도입니다.

 

그리고, D만큼만 반복하게끔하여 현재 쏴야 할 높이를 알아냅니다. 높이를 알아냈다면 해당 높이의 건물이 몇 개인지 cntNum으로 알아내고 i번째 cache에 넣어줍니다. 그리고, 높이를 깎았으니 높이에 대한 -1 값을 pq에 push 하고, cntNum[높이 - 1]에도 현재 쏜 건물의 개수만큼 추가적으로 생기기 때문에 높이의 대한 건물 개수를 더해줍니다.

이 과정을 D만큼만 반복합니다.

 

풀 때 당시에는 DP라 생각하고 풀었지만, 이제 보니 Prefix Sum이었습니다. D만큼 반복하여

cache_N = cache_N-1 + cache_N 다음과 같은 점화식을 통해 문제를 풀 수 있었습니다.

 

추가적으로 생각난 거지만 최댓값을 미리 구해두고, 어차피 한 번 쏠 때마다 1씩 깎이기 때문에 굳이 우선순위 큐를 사용하지 않아도 될 거 같았습니다.

 

+ 다른 분들의 코드를 봤더니 max_element 함수를 대부분 사용하신 걸 봤습니다. 까먹고 있던 함수인데 공부해봐야겠습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define MAX 300001
using namespace std;

int N, D;
ll cntNum[MAX];
ll cache[MAX];

struct cmp{
    bool operator()(int a,int b){
        return a < b;
    }
};

int main(){
    FASTIO
    cin >> N >> D;
    priority_queue<int, vector<int>, cmp> pq;
    for(int i = 0, a; i < N; i++){
        cin >> a;
        if(!cntNum[a]) pq.push(a);
        cntNum[a]++;
    }
    
    for(int i = 0; i < D; i++){
        if(pq.empty()) continue;
        int h = pq.top();
        if(h == 0) break;
        cache[i] = cntNum[h];
        pq.pop();
        
        if(pq.top() != h - 1) pq.push(h - 1);
        cntNum[h - 1] += cntNum[h];
    }
    
    
    for(int i = 1; i < D; i++){
        cache[i] = cache[i - 1] + cache[i];
    }
    
    cout << cache[D - 1];
    return 0;
}