프로그래밍

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

[난이도] Silver1
[유형] 우선순위큐

[풀이]
우선순위 큐에 모든 원소들을 넣고 가장 작은 두 수를 뽑아서 계산해서 다시 넣어주고 반복하면 됩니다.

#include <cstdio>
#include <queue>
using namespace std;
int n,m;
using ll = long long;
int main(){
    scanf("%d%d",&n,&m);
    priority_queue<long long> pq;
    while(n--) {
        int v;
        scanf("%d",&v);
        pq.push(-v);
    }
    while(m--){
        ll a = pq.top(); pq.pop();
        ll b = pq.top(); pq.pop();
        pq.push(a+b);
        pq.push(a+b);
    }
    ll ans=0;
    while(!pq.empty()) ans+=pq.top(), pq.pop();
    printf("%lld",-ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/15903.cpp

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

[난이도] Gold1
[유형] 우선순위큐

[풀이]
struct P{
    int id,t,pos;
}
id : id, t : 계산이 끝나는 시간, pos :계산대의 위치
위와 같이 구조체를 정의해줍니다. 그리고
우선순위큐의 comparator 객체를 정의하여
끝나는 시간 t가 작을수록 , 출구에 가까운 계산대 (pos가 클수록)
top에 오도록 해줍니다.

그 뒤 매 루프마다 끝나는 시간이 빠른 모든 원소들을 pop 해준 뒤
ans vector에는 id를 저장해줍니다. 출구쪽부터 pop되기 때문에 이 순서로 ans vector에 저장해주면 됩니다.

rp vector에는 pop되는 순서대로 pos를 저장해줍니다. 이 rp vector를 뒤집은 뒤 반대로 순회하면서
나온 pos에 순차적으로 고객들을 push해줍니다. 시간은 현재 pop된 t+(고객의 물건 수)를 해주면
끝나는 시간을 넣어줄 수 있습니다.

위 과정을 반복하면서 ans vector를 채워주면 정답을 구할 수 있습니다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int N,k;
pair<int,int> a[1000000];
struct P{
    int id,t,pos;
}; 
struct cmp{
    bool operator()(P& a,P& b){
        if(a.t > b.t) return true;
        else if(a.t == b.t){
            if(a.pos<b.pos) return true;
        }
        return false;
    }
};
int main(){
    scanf("%d%d",&N,&k);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    priority_queue<P,vector<P>,cmp> pq;
    int i=0;
    for(;i<N&&i<k;i++) pq.push({a[i].first,a[i].second,i});
    vector<int> ans;
    for(;i<N;i++){
        auto [id,t,pos] = pq.top();
        vector<int> rp;
        while(!pq.empty() && pq.top().t==t){
            rp.push_back(pq.top().pos);
            ans.push_back(pq.top().id);
            pq.pop();
        }
        reverse(rp.begin(),rp.end());
        for(auto r : rp){
            pq.push({a[i].first,t+a[i].second,r});
            i++;
            if(i>=N) break;
        }
        i--;
    }
    while(!pq.empty()){
        auto [id,t,pos] = pq.top(); pq.pop();
        ans.push_back(id);
    }
    long long total=0;
    for(int i=1;i<=N;i++) total+=i*(long long)ans[i-1];
    printf("%lld",total); 
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/17612.cpp

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

[난이도] Gold4
[유형] 우선순위큐

[풀이]
https://www.acmicpc.net/problem/11066 문제와 다른점은
꼭 연속된 파일을 합칠 필요가 없이 아무 파일이나 두개를 골라서 합쳐도 된다는 것입니다.

우선순위큐에 모든 파일의 크기를 넣어놓고 작은 것부터 꺼내서 합친 뒤, 다시 넣고를 반복하다
최종적으로 남게되는 1개의 파일의 크기가 최종 정답입니다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
using ll = long long;
int T,K;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&K);
        priority_queue<ll,vector<ll>,greater<ll>> pq;
        for(int i=0;i<K;i++) {
            int v;
            scanf("%d",&v);
            pq.push(v);
        }
        ll ans=0;
        while(pq.size()>1){
            ll a = pq.top(); pq.pop();
            ll b = pq.top(); pq.pop();
            pq.push(a+b);
            ans+=a+b;
        }
        printf("%lld\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13975.cpp

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

[난이도] Silver1
[유형] 우선순위큐

[풀이]
우선순위큐

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val pq = PriorityQueue<Int>()
    var N = readLine().toInt()
    while(N-->0){
        var k = readLine().toInt()
        when(k){
            0 -> {
                var t = 0
                pq.poll()?.let{
                    t+=it
                }
                println(t)
            }
            else -> pq.add(k)
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1927.cpp

var default_pq = PriorityQueue<Int>()
default_pq.add(5)
default_pq.add(3)
default_pq.add(7)
println("default")
while(!default_pq.isEmpty()){
println(default_pq.poll())
}
// default
// 3
// 5
// 7

var reverse_pq = PriorityQueue<Int>{a,b-> b.compareTo(a)}
reverse_pq.add(5)
reverse_pq.add(3)
reverse_pq.add(7)

println("reverse")
while(!reverse_pq.isEmpty()){
println(reverse_pq.poll())
}
// reverse
// 7
// 5
// 3

var pq = PriorityQueue<T>()

와 같이 우선순위큐를 생성할 수 있습니다.

C++과 다르게 comparator 전달 없이 생성하면 pop시에 작은 수부터 나오게 됩니다.

 큰 수부터 나오게 하기 위해서는 두번째 예와 같이 람다 comparator를 전달해주면 됩니다.

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

[난이도] Gold5
[유형] 우선순위큐

[풀이]
N자리에서 K자리를 지워야 하므로
N-K 자리의 수를 만들어야 한다.
가장 큰 자리수에 큰 수가 올수록 유리하다.
큰 자리수의 숫자부터 b[0]~b[N-1]에 저장하기로 하면
b[0]은 a[0]~a[N-K] 중에 가장 큰수,
b[1]은 (b[0]의 a에서의 index)~a[N-K+1] 중에 가장 큰수,
b[2]은 (b[1]의 a에서의 index)~a[N-K+2] 중에 가장 큰수
....
으로 구할 수 있다.
그런데 for문으로 큰 수들을 구하면 시간초과가 나므로 우선순위 큐를 이용하였다.

a 배열에서 0~N-K-1 까지의 수를 pq에 {a[i],i} pair로 index까지 같이 넣어놓고
K번의 반복동안
N-K+i번 pair를 추가하면서 pq에서 최댓값을 찾으면 NlogN의 시간으로 답을 찾을 수 있다.

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N,a[500000],K;

struct cmp{
    bool operator()(pair<int,int> a,pair<int,int> b){
        if(a.first<b.first) return 1;
        else if(a.first==b.first) return a.second > b.second;
        return 0;
    }
};
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%1d",&a[i]);
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
    K=N-K;
    for(int i=0;i<N-K;i++) pq.push({a[i],i});
    int s=-1,e;
    for(int i=0;i<K;i++){
        e=N-K+i;
        pq.push({a[e],e});
        while(!pq.empty()){
            auto qt = pq.top(); pq.pop();
            if(qt.second>s) {
                s=qt.second;
                break;
            }
        }
        printf("%d",a[s]);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2812.cpp

www.acmicpc.net/problem/2075

[난이도] Gold4

[유형] 우선순위큐

[풀이]

메모리 제한이 12MB으로 적으므로 우선순위 큐를 이용해서 푼다.
큐의 크기가 N 이하이면 무조건 push,
아닌 경우 top보다 작은 것들은 무시, top보다 크면 pop하고 push한다
모든 수를 다 봤을 때 top이 정답이다.

#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int N;
int main(){
    priority_queue<int,vector<int>,greater<int>> a;
    scanf("%d",&N);
    for(int i=0;i<N*N;i++) {
        int v;
        scanf("%d",&v);
        if(a.size()<N) a.push(v);
        else if(a.top() < v) {
            a.pop();
            a.push(v);
        }
    }
    printf("%d",a.top());
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2075.cpp

www.acmicpc.net/problem/1715

[난이도] Gold4

[유형] 우선순위큐

[풀이]

가장 작은 것부터 두개씩 뽑고, 두개의 합을 다시 큐에 넣으면 된다.

#include <cstdio>
#include <queue>
using namespace std;
int main(){
    priority_queue<int> pq;
    int N,a,ret=0;
    scanf("%d",&N);
    while(N--) scanf("%d",&a), pq.push(-a);
    while(pq.size()>1){
        int u,v;
        u=pq.top(); pq.pop();
        v=pq.top(); pq.pop();
        ret+=-u-v;
        pq.push(u+v);
    }
    printf("%d",ret);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1715.cpp