백준 BOJ 우선순위 큐(Priority Queue) 문제 풀이 220825
백준 BOJ 13904번 : 과제
문제 난이도 : Gold III
알고리즘 분류 : 그리디, 우선순위 큐
N개의 과제들의 남은 날짜 수와 그 과제의 점수가 주어질 때, 하루에 하나씩 과제를 하여 얻을 수 있는 점수의 최댓값을 구하는 문제이다.
먼저 문제들을 남을 일 수를 기준으로 오름차순 정렬해준 뒤, 우선순위 큐에 할 과제들만 남겨보자.
우선순위 큐에 과제를 하나씩 넣고 만약 우선순위 큐의 size가 방금 넣은 날짜 수보다 많다면 같아질 때까지 빼주면 된다.
i번째 과제를 넣는 과정을 통해 i일까지 할 과제들을 우선순위 큐에 남긴다고 생각하면, 하루에 한 개씩 과제를 할 수 있으므로 i보다 많은 수의 과제가 들어있으면 안되기 때문이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++)
cin >> v[i].first >> v[i].second;
sort(v.begin(), v.end());
priority_queue<int, vector<int>, greater<int>> pq;
for(int i=0; i<N; i++) {
pq.push(v[i].second);
while(v[i].first < pq.size()) pq.pop();
}
int ans = 0;
while(!pq.empty()) {
ans += pq.top();
pq.pop();
}
cout << ans << "\n";
}
백준 BOJ 2109번 : 순회강연
문제 난이도 : Gold III
알고리즘 분류 : 그리디, 우선순위 큐
N개의 강연 목록이 있고, 각 강연은 d일 안에 가서 하면 p의 보상을 받을 수 있다.
하루에 한 개씩 강연을 할 때 최대로 얻을 수 있는 보상의 합을 구하는 문제이다.
위의 문제와 동일하다.
입력부만 v[i].second, v[i].first 순으로 받아주면 동일한 코드로 풀린다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++)
cin >> v[i].second >> v[i].first;
sort(v.begin(), v.end());
priority_queue<int, vector<int>, greater<int>> pq;
for(int i=0; i<N; i++) {
pq.push(v[i].second);
while(v[i].first < pq.size()) pq.pop();
}
int ans = 0;
while(!pq.empty()) {
ans += pq.top();
pq.pop();
}
cout << ans << "\n";
}
백준 BOJ 9869번 : Milk Scheduling
문제 난이도 : Gold III
알고리즘 분류 : 그리디, 우선순위 큐
농부가 소들의 젖을 짜는데 그 후보가 N마리이고, 각각 얻을 수 있는 우유의 양과 특정 순서 내에서만 짤 수 있는 번호가 주어질 때, 농부가 얻을 수 있는 우유의 최대 양을 구하는 문제이다.
위의 문제들과 동일한 문제이며, BOJ 2109 풀이와 동일한 소스 코드로 풀린다.
백준 BOJ 1781번 : 컵라면
문제 난이도 : Gold III
알고리즘 분류 : 그리디, 우선순위 큐
N개의 문제들의 데드라인과 그 문제를 풀었을 때 받을 수 있는 컵라면이 주어지고, 단위 시간 당 1개의 문제만 풀이할 수 있을 때 받을 수 있는 컵라면의 최댓값을 구하는 문제이다.
위의 문제들과 동일한 문제이며, BOJ 13904 풀이와 동일한 코드로 풀린다.
백준 BOJ 1374번 : 강의실
문제 난이도 : Gold V
알고리즘 분류 : 우선순위 큐
N개 강의의 시작 시간과 끝나는 시간이 주어질 때, 한 강의는 한 강의실에서만 하고 모든 강의를 진행하기 위해서는 최소 몇 개의 강의실이 필요한지 구하는 문제이다.
시작 시간이 증가하는 순으로 오름차순 정렬을 해주고, 우선순위 큐에 강의가 끝나는 시간을 push 해주고 다음 강의와 비교할 때 시작 시간보다 먼저 끝나는 강의들은 pop을 해주는 과정을 반복한다.
이 때 pq의 size가 최대가 될 때의 크기가 답이 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++) {
int x;
cin >> x >> v[i].first >> v[i].second;
}
sort(v.begin(), v.end());
priority_queue<int, vector<int>, greater<int>> pq;
int ans = 0;
for(int i=0; i<N; i++) {
while(!pq.empty() && pq.top() <= v[i].first) pq.pop();
pq.push(v[i].second);
ans = max(ans, (int)pq.size());
}
cout << ans << "\n";
}
백준 BOJ 19598번 : 최소 회의실 개수
문제 난이도 : Gold V
알고리즘 분류 : 우선순위 큐
N개의 회의의 시작 시간과 종료 시간이 주어질 때, 필요한 최소 회의실의 개수를 구하는 문제이다.
위의 문제와 동일하다.
회의 번호가 없다는 것만 빼고는 나머지는 동일한 코드로 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++) cin >> v[i].first >> v[i].second;
sort(v.begin(), v.end());
priority_queue<int, vector<int>, greater<int>> pq;
int ans = 0;
for(int i=0; i<N; i++) {
while(!pq.empty() && pq.top() <= v[i].first) pq.pop();
pq.push(v[i].second);
ans = max(ans, (int)pq.size());
}
cout << ans << "\n";
}
백준 BOJ 5619번 : 세 번째
문제 난이도 : Silver II
알고리즘 분류 : 그리디
N개의 수가 주어질 때, 두 수를 이어붙여 만든 수들 중 세 번째로 작은 수를 구하는 문제이다.
수를 오름차순으로 정렬하여 i번째로 작은 수를 ai라고 하자.
그럼 a1a4가 a2a1, a3a1 a2a3 등보다 작을 수가 있다.
따라서 a4까지는 조합을 해본 뒤 정렬을 해서 답을 구해주어야 한다.
즉, 4C2 x 2 = 12가지 수들을 벡터에 넣고 정렬한 뒤 3번째로 작은 값을 답으로 구해주면 된다.
원래는 우선순위 큐로도 풀 수 있는 문제라고 하지만, 이 풀이가 더 간단해 보여서 이렇게 풀었다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
vector<int> u;
string a = to_string(v[0]);
string b = to_string(v[1]);
string c = to_string(v[2]);
u.push_back(stoll(a + b));
u.push_back(stoll(b + a));
u.push_back(stoll(b + c));
u.push_back(stoll(c + b));
u.push_back(stoll(c + a));
u.push_back(stoll(a + c));
if(N >= 4) {
string d = to_string(v[3]);
u.push_back(stoll(a + d));
u.push_back(stoll(b + d));
u.push_back(stoll(c + d));
u.push_back(stoll(d + a));
u.push_back(stoll(d + b));
u.push_back(stoll(d + c));
}
sort(u.begin(), u.end());
cout << u[2] << "\n";
}
백준 BOJ 13984번 : Contest Score
문제 난이도 : Silver II
알고리즘 분류 : 우선순위 큐
N개의 각 문제의 푸는 시간이 주어질 때, 앞에서 M개의 문제를 보고 시간이 가장 적게 드는 것을 풀고 그 다음 2 ~ M+1번째 문제들에 대해 같은 과정을 반복하고, ... 하여 모든 문제를 푸는데 걸리는 시간 페널티의 합을 구하는 문제이다.
우선순위 큐를 이용하여 M개의 값을 담고, 그 중 가장 시간이 적은 것을 sum 값에 더하고, 이 sum 값을 ans에 더하는 과정을 반복해주면 된다.
마지막 N-M개 자료에 대해서는 더 이상 입력을 받지 않고 큐에서 pop 하는 과정만 반복해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
priority_queue<int, vector<int>, greater<int>> pq;
for(int i=0; i<M; i++) {
int x; cin >> x;
pq.push(x);
}
int ans = 0, sum = 0;
for(int i=0; i<N-M; i++) {
sum += pq.top();
ans += sum;
pq.pop();
int x; cin >> x;
pq.push(x);
}
while(!pq.empty()) {
sum += pq.top();
ans += sum;
pq.pop();
}
cout << ans << "\n";
}
백준 BOJ 23757번 : 아이들과 선물 상자
문제 난이도 : Silver II
알고리즘 분류 : 우선순위 큐
1번부터 N번까지 상자에 들어있는 선물들의 개수가 주어지고, 1번부터 M번 사람까지 원하는 수의 선물이 있을 때, 1번 사람부터 순서대로 나와 남아있는 선물들 중 가장 개수가 많은 것에서 원하는 개수를 가져가고 남은 선물들은 그대로 둘 때, 모든 사람이 선물을 가져갈 수 있는지의 여부를 구하는 문제이다.
우선순위 큐를 활용하여, 먼저 N개의 수를 넣어 놓고 1번부터 M번 사람까지 순서대로 우선순위 큐의 top에 있는 값과 비교를 하여 원하는 값이 top보다 큰 경우가 있으면 0을 출력해주면 된다.
이 문제를 푸는데 우선순위 큐를 사용하는 것이 수월한 이유는 남은 값을 빼서 구해준 다음 다시 pq에 넣어주기만 하면 되기 때문이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
priority_queue<int, vector<int>> pq;
while(N--) {
int x; cin >> x;
pq.push(x);
}
bool b = true;
while(M--) {
int x; cin >> x;
if(x > pq.top()) {
b = false;
break;
}
int tmp = pq.top() - x;
pq.pop();
if(tmp > 0) pq.push(tmp);
}
if(b) cout << 1 << "\n";
else cout << 0 << "\n";
}
백준 BOJ 25101번 : Robin Hood
문제 난이도 : Silver II
알고리즘 분류 : 우선순위 큐
N명의 사람의 재산이 있을 때, 도둑이 현재 남은 돈이 가장 많으면서 앞 번호에 있는 사람의 돈을 100원씩 가져간다고 할 때, M번 가져간 후에 남은 사람들의 재산을 구하는 문제이다.
먼저 우선순위 큐로 풀이하는 방법을 생각할 수 있다.
문제는 M번의 연산 이후 남은 돈을 순서 그대로 출력해야 한다는 것인데, 이것은 pq 값에 주소까지 넣어서 처리할 수 있다.
같은 돈을 가진 사람이 여러 명이면 앞에 있는 사람의 돈을 가져가므로, 돈은 내림차순으로하되 주소는 오름차순으로 넣어주어야 한다. (나의 경우에는 주소 값에 그냥 마이너스 부호를 붙여서 주소가 클수록 더 큰 음수가 되어 먼저 나오게 하였다.)
이제 pq에서 하나씩 값을 뽑으면서 100을 빼는 연산을 하되, 더 이상 뺄 수 없는 경우는 bool 변수에 기록을 해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
vector<int> v(N);
for(int i=0; i<N; i++) {
cin >> v[i];
pq.push({v[i], -i});
}
bool b = true;
while(M--) {
if(pq.top().first <= 100) {
b = false;
break;
}
int x = pq.top().first;
int y = -pq.top().second;
pq.pop();
v[y] -= 100;
pq.push({x - 100, -y});
}
if(b) {
for(int i=0; i<N; i++) cout << v[i] << " ";
cout << "\n";
}
else cout << "impossible\n";
}