[BOJ 28703] Double It

우선순위 큐 문제

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

 

 

---

[문제 설명]

 

구해야 하는 답이 매 순간마다의 최댓값과 최솟값의 차이고, 가능한 연산은 2를 곱해주는 것밖에 없으므로 어렵지 않게 최소 우선순위 큐를 떠올릴 수 있을 겁니다. 그러나 이 문제가 어려워 보이는 이유는 2를 곱하는 연산에 대해 횟수 제한이 없기 때문입니다. A의 원소들에 대해 적절히 2를 곱해주는 작업을 얼마나 해야 차가 최소가 되는지 직관적으로 알 수 없기 때문에 어려워 보입니다.

 

 

배열 A의 최솟값이 $m$, 최댓값이 $M$, $M - m$을 $r$이라고 하겠습니다.

A의 모든 원소에 2를 곱해보겠습니다. 최솟값은 $2m$, 최댓값은 $2M$이 되고, 차를 구하면 $2(M-m) = 2r$이 됩니다. A의 모든 원소에 $2^p (0 < p)$가 곱해지면 분배법칙에 의해 r에 $2^k (0 < k \leq p)$가 곱해지게 되므로 오히려 손해라는 것을 알 수 있습니다.

최소 우선순위 큐에서 값들을 꺼내서 2를 곱하는 과정을 반복하다보면 당연히 언젠가는 모든 원소에 적어도 2가 곱해지는 순간이 올 것이고 그 순간은 당연히 배열의 최초 상태에서 가장 컸던 값에 2가 곱해지는 순간일 것이므로 그때 반복문을 종료하면 됩니다.

 

 

해결 방법을 정리하자면

 

1. 최초 배열 내의 최댓값을 기록한 후에 배열의 모든 값을 최소 우선순위 큐에 집어 넣습니다.
2. 최솟값을 계속 꺼내면서 2를 곱하고 다시 넣어주는 과정을 반복합니다.
3. 반복하면서 우선순위 큐 내에 있는 최솟값과 최댓값의 차를 구해서 그 중 가장 작은 값이 정답입니다. 최소 우선순위 큐를 사용하므로 현재 최댓값은 따로 저장해두면 됩니다.
4. 최솟값이 최초 최댓값이 된다면 반복을 멈추면 됩니다. (바꿔 말해서 최초 최댓값을 제외한 모든 배열의 값이 최소 한 번 이상 2로 곱해졌다면 반복을 멈추면 됩니다.)

모든 원소들에 대해 2를 곱해주는 작업을 하게 될 것이므로 $O(N)$, 하나의 원소가 최초 최댓값보다 커지기 위해서 걸리는 시간은 $O(\log A)$, 우선순위 큐에서 원소를 넣고 빼는 작업이 $O(\log N)$이므로 총 시간 복잡도는 $O(N (\log A + \log N))$이므로, A의 상한이 아무리 $10^9$더라도 통과가 가능합니다.

 

---

[소스 코드] / C++

 

설명은 우선순위 큐로 설명했지만, 1이 199,999개, 10^9이 1개 있으면 매우 오래 걸릴 것이므로 아주 약간의 시간 절약을 위해 set을 사용하였습니다.

 

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

set<int> st;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int N; cin >> N;
    
    for (int i = 0; i < N; i++) {
        int n; cin >> n;
        st.insert(n);
    }

    int M = *(st.rbegin());
    int m = M;
    int ans = 2000000001;

    while (1) {
        int cur = *(st.begin());
        st.erase(st.begin());
        ans = min(ans, m-cur);

        if (cur == M) break;

        if (cur*2 <= m) {
            while (cur*2 <= m) {
                cur*=2;
            }
        } else {
            cur *= 2;
            m = cur;
        }
        
        st.insert(cur);
    }

    cout << ans;

    return 0;
}