[백준 31963번] 두 배

문제 링크

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

(2024 KOI 1차대회 초등부 2번, 중등부 1번)

 

문제 요약

길이가 N인 수열이 주어졌을 때, 수열의 한 원소에 숫자 2를 곱하는 연산을 할 수 있다. 이때 주어진 수열을 오름차순으로 만들 수 있는  최소한의 연산 횟수를 구하는 문제이다.

 

문제 풀이

시뮬레이션으로 문제 풀기(부분점수)

수열의 두 번째 원소부터 마지막 원소까지 순회하면서, 각 원소가 이전 원소보다 커질 때까지 2를 곱하는 과정을 반복하고, 그 횟수를 직접 계산하는 방법으로 문제를 풀 수 있다.

int simulate(const vector<int>& vi) {
    vector<int> incresing_order(vi.size());
    incresing_order[0] = vi[0];
    
    int ret = 0;
    
    for (int i = 1 ; i < vi.size() ; ++i) {
        incresing_order[i] = vi[i];
        
        while (incresing_order[i] < incresing_order[i - 1]) {
            incresing_order[i] *= 2;
            ++ret;
        }
    }
    
    return ret;
}

하지만 이 방법으로는 만점을 받을 수 없고 부분점수만 받을 수 있다. 예를 들어, 1,000,000부터 시작해 1씩 감소하는 수열이 주어졌을 때를 생각해 보자. 이 경우가 최악의 사례인데, 이때 시간복잡도는 \(\mathcal{O}(N^2)\)이므로 N이 최대일 때는 주어진 시간 내에 문제를 해결할 수 없다. 따라서 만점을 받기 위해서는 다른 방법이 필요하다.

 

수식으로 정리해서 문제 풀기

\(i-1\)번째 원소 \(A_{i-1}\)에 2가 곱해진 횟수를 \(x\)라고 하고, \(i\)번째 원소 \(A_{i}\)에 2가 곱해진 횟수를 \(y\)라고 하자. 이때 수열이 오름차순이 되려면 다음과 같은 수식을 만족해야 한다.

$$A_{i-1} \times 2^x \leq A_{i} \times 2^y$$

그 다음 \(y\)를 제외한 나머지 모든 항을 왼쪽으로 정리한다.

$$\frac{A_{i-1}}{A_{i}} \times 2^x \leq 2^y$$

이제 양쪽 항 모두에 \(log_2\)를 적용하고, 로그의 곱셈 및 나눗셈 법칙을 이용해 정리한다.

$$log_2 \frac{A_{i-1}}{A_{i}} + x \leq y$$

만약 \(i - 1\)번째 원소 \(A_{i-1}\)에 2를 곱한 횟수 \(x\)를 알고 있다면, 앞서 정리한 수식을 이용해 마지막 원소까지 2를 곱해야 하는 횟수를 모두 구할 수 있다. 첫 번째 원소에는 2를 곱하는 않는 것이 유리하므로, \(i - 1\)이 1일 때 \(x\)는 0으로 정해져 있다. 이 사실을 활용하면 문제의 답을 구할 수 있다. 답이 int 범위가 넘어갈 수 있으므로 long long 자료형을 사용해야 한다는 것에 유의하자.

long long solve(const vector<int>& vi) {
    long long ret = 0;
    
    vector<int> multiply_cnt(vi.size(), 0);
    
    for (int i = 1 ; i < vi.size() ; ++i) {
        multiply_cnt[i] = max((int)ceil(log2((double)vi[i - 1]/ (double)vi[i]) + (double)multiply_cnt[i - 1]), 0);
        
        ret += multiply_cnt[i];
    }
    
    return ret;
}

사실 위 코드는 부동소수점 연산의 정확도 문제 때문에 잠재적인 위험이 있다. 정확한 로그 값이 필요한 것이 아니라 올림(ceil) 연산을 한 값이 필요하기 때문에 vi[i - 1]과 v[i]에 직접 log2 연산을 하지 않아도 된다. 대신 vi[i - 1]에 2를 몇 번 곱해야 vi[i]보다 커지는지 혹은 vi[i - 1]에 2를 몇 번 나눠야 v[i]보다 작아지는지를 계산해 둔다면 ceil과 똑같은 기능을 기대할 수 있다. 이렇게 한다면 부동소수점 연산이 가지고 있는 부정확함에 벌벌 떨지 않아도 될 것이다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long long solve(const vector<int>& vi) {
    long long ret = 0;
    
    vector<int> multiply_cnt(vi.size(), 0);
    
    for (int i = 1 ; i < vi.size() ; ++i) {
        multiply_cnt[i] = max((int)ceil(log2((double)vi[i - 1]/ (double)vi[i]) + (double)multiply_cnt[i - 1]), 0);
        
        ret += multiply_cnt[i];
    }
    
    return ret;
}

int main() {
    int n;
    
    cin >> n;
    
    vector<int> vi(n);
    
    for (int i = 0 ; i < n ; ++i) {
        cin >> vi[i];
    }
    
    long long ans = solve(vi);
    
    cout << ans << endl;
}