- 문제
센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다.
거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다.
센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.
하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.
과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?
//시간 제한: 1초, 메모리 제한: 1024MB
- 입력
첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다.
두 번째 줄부터 N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.
- 출력
마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.
마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 이용하고도 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.
// Created by dongwan-kim on 2022/07/25.
#include<iostream>
#include<deque>
#include<queue>
#include<algorithm>
using namespace std;
int n, h, t, m, cnt, k;
priority_queue<int> pq;
int main() {
cin >> n >> h >> t;
for (int i = 0; i < n; i++) { //거인의 키 입력
cin >> m;
if (m >= h) { //센티보다 작은 거인은 push해주지 않았다.
pq.push(m);
}
}
while (!pq.empty()) {
k = pq.top() / 2;
cnt++; //뿅망치를 사용한 횟수
if (k == 0) { //테케 마지막과 같은 예외를 처리해 주는 부분이다. 키가 1인 경우 더 줄어들 수 없는 상황
cout << "NO" << "\n";
cout << cnt;
return 0;
}
if (k < h) { //뿅망치를 맞고 센티보다 키가 작아진 거인을 pop해준다
pq.pop();
} else { //뿅망치를 맞고도 센티보다 키가 큰 거인을 이전 키를 빼고 절반이 된 키를 다시 push
pq.pop();
pq.push(k);
}
if (cnt == t) //뿅망치 횟수제한과 사용한 뿅망치 횟수가 같아지면 반복문을 탈출한다.
break;
}
if (pq.empty()) { //더이상 센타보다 키가 크거나 같은 거인이 없다면
cout << "YES" << "\n";
cout << cnt;
} else {
cout << "NO" << "\n";
cout << pq.top();
}
}풀이
뿅망치를 효율적으로 사용하기 위한 전략이 매번 가장 키가 큰 거인을 먼저 때리는 것이므로 정렬이 필요하다 생각했고, 삽입과 삭제가 빠른 자료구조를 고민하다가 pq를 떠올리게 되었다.
pq는 max로 구현되어 있고, 삽입 삭제가 될 때 알아서 정렬되며 자리를 찾아가기 때문에 효율적으로 코드를 구현했다고 생각한다.
자세한 구현 내용은 주석에 나와있다.
KIM DONGWAN