※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 28068번 문제인 I Am Knowledge이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/28068
28068번: I Am Knowledge
저택에 살고 있는 마법사는 지하의 도서관에 자주 방문한다. 어느 날, 마법사는 도서관에 있는 책
www.acmicpc.net
각 책을 (a,b)와 같이 나타낸다면, 해당 책은 마법사의 즐거움이 a 이상일 때 읽어 즐거움을 b-a만큼 증가시켜줄 수 있다. (단, b-a가 음수이면 a-b만큼 감소한다.) 모든 책을 읽는 방법이 존재한다면 순서를 적절히 조절해 '책을 읽기 전과 비교했을 때 읽은 뒤 즐거움이 증가하는 책'들을 모두 읽고 그렇지 않은 책들을 마저 읽어 모든 책을 읽을 수도 있음을 관찰하자.
읽은 뒤 즐거움이 증가하는 책들을 조건을 만족하도록 전부 읽는 것이 가능한지는 그러한 책들을 a값을 기준으로 오름차순 정렬했을 때 이 책들을 그 순서대로 읽어나갈 수 있는지를 확인하는 것으로 해낼 수 있다.
읽은 뒤 즐거움이 감소하는 책들을 차례대로 읽을 수 있는지를 생각해보자. 만약 그러한 방법이 존재한다면 모든 책을 다 읽었을 때의 최종 즐거움 값은 (모든 b의 값의 합) - (모든 a의 값의 합)이 될 것이다. 이 즐거움 값에서 시작해 즐거움이 감소하는 책을 읽어나가던 과정을 거꾸로 실행해나가는 것은 '현재 즐거움 값이 b 이상일 때 읽어 즐거움을 a-b(>0)만큼 증가시키는' 책을 읽어나가는 것으로 생각할 수 있다. 이것이 앞선 문단의 경우와 동일함을 관찰하면 이 또한 같은 방법으로 해결할 수 있음을 알 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int N;
vector<pair<int, int>> vec1, vec2;
ll val1, val2;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
while (N--) {
int a, b; cin >> a >> b;
val1 += (b - a);
if (a > b) vec1.emplace_back(make_pair(b, a - b));
else vec2.emplace_back(make_pair(a, b - a));
}
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
for (auto& p : vec1) {
if (val1 < p.first) {
cout << 0;
return 0;
}
val1 += p.second;
}
for (auto& p : vec2) {
if (val2 < p.first) {
cout << 0;
return 0;
}
val2 += p.second;
}
cout << 1;
}'BOJ' 카테고리의 다른 글
| [BOJ 28070 // C++] 유니의 편지 쓰기 (1) | 2023.12.02 |
|---|---|
| [BOJ 28069 // C++] 김밥천국의 계단 (0) | 2023.12.01 |
| [BOJ 28067 // C++] 기하가 너무 좋아 (0) | 2023.11.29 |
| [BOJ 28066 // C++] 타노스는 요세푸스가 밉다 (0) | 2023.11.28 |
| [BOJ 28065 // C++] SW 수열 구하기 (1) | 2023.11.27 |