[ 백준 28703 ] Double It (c/c++)

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

 

 

[ 문제 요약 ]

N개의 정수가 주어질 때 원하는 수 하나를 골라서 2를 곱해서 최대값과 최솟값의 차이의 최솟값을 출력한다.

 

 

[ 문제풀이 ]

1. 최대값과 최솟값이 필요하므로 우선순위 큐를 두 개를 만든다.

2. 만약 모든 수에 최소한 한 번 이상 2를 곱했다면 이후에는 동일한 양상으로 곱해지는데 2가 곱해진 상태에서 차이를 구하게 되어 최솟값이 될 수 없다. 즉, 최솟값이 원래 배열의 최대값을 넘는 순간까지만 보면 된다.

3. 최솟값과 최대값을 구한 뒤 각 우선순위 큐에 최솟값의 2배를 넣는다.

4. 2번 조건을 만족하는 동안 반복해서 최솟값을 구한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, high, num, ans = 1234567890;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;

int main() {
    cin >> N;
    for (int i=0; i<N; i++) {
        cin >> num;
        max_pq.push(num);
        min_pq.push(num);
    }
    high = max_pq.top();
    
    while (min_pq.top() <= high){
        ans = min(ans, max_pq.top() - min_pq.top());
        num = min_pq.top() * 2;
        min_pq.pop();
        max_pq.push(num);
        min_pq.push(num);
    }
    cout << ans;
    
    return 0;
}

 

 

[ 주의할 점 ]

우선순위 큐의 경우 최대값 또는 최솟값이 top에 오도록 지정할 수 있고, while문의 종료 조건을 잘 생각해야 하는 문제였다.