[BOJ] 31963 - 두 배

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

BOJ - 두 배

문제 유형: 수학, 그리디

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 1024MB

 

문제

길이 N인 양의 정수열 A1,…,AN이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 A1,…,AN이 오름차순이라는 것은, 각 i (1≤i≤N−1)에 대해 Ai≤Ai+1이라는 것이다.

수열 A를 오름차순으로 만들기 위해, 수열 A에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

• 어떤 i (1≤i≤N)에 대해 Ai에 2를 곱한다.

연산을 최소 횟수로 적용해서 A를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.

 

입력

첫 번째 줄에 N이 주어진다.

두 번째 줄에 A1,…,AN이 주어진다.

 

• 주어지는 모든 수는 정수이다.
•  1≤N≤250000
•  1≤Ai≤1000000

 

출력

첫 번째 줄에 답을 출력한다.

 

풀이

우선, 입력받은 수를 lsb가 1이 될 때까지 2로 왼쪽 시프트를 시키고, 그 횟수만큼 따로 배열에 저장한다.

그렇게 시프트된 수를 base라 하자.

그의 길이 baselen도 구해준다.

 

1번부터 n-1번까지의 수에 대해서, 순차적으로 이전 인덱스의 수와 비교한다.

i번째 수면, i-1번째 수와 비교하면 되는것이다.

이전 수의 baselen과 맞춰서 두 수를 (같은 길이의 base 비트) * (2^n)의 꼴로 정규화시킨다.

이렇게 정규화하면, 이전 수에 2의 승수를 얼마나 곱해야 하는지 답이 나온다.

이 곱한 값들을 모두 누적해서 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> arr(n), baselen(n), exps(n), more_exps(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        while (arr[i] % 2 == 0) {
            arr[i] >>= 1;
            exps[i]++;
        }
        baselen[i] = 64 - __builtin_clzll(arr[i]);
    }

    for (int i = 1; i < n; i++) {
        ll prevbaselen = baselen[i - 1];
        ll prevbase = arr[i - 1];
        ll prevexp = exps[i - 1] + more_exps[i - 1];

        ll curbaselen = baselen[i];
        ll curbase = arr[i];
        ll curexp = exps[i];

        if (prevbaselen < curbaselen) {
            ll lendiff = curbaselen - prevbaselen;
            prevbase <<= lendiff;
            prevexp -= lendiff;
        } else if (curbaselen < prevbaselen) {
            ll lendiff = prevbaselen - curbaselen;
            curbase <<= lendiff;
            curexp -= lendiff;
        }

        ll expdiff = prevexp - curexp;
        if (expdiff > 0) more_exps[i] = expdiff;
        if (curexp <= prevexp && curbase < prevbase) more_exps[i]++;
    }

    cout << accumulate(more_exps.begin(), more_exps.end(), 0LL) << "\n";

    return 0;
}