[BOJ] 두 배 - Compy's Blog

두 배

TimeLimit	MemoryLimit	Condition	TAG
1s	1024MB	(1<=N <= 250000, 1 <= A_i <= 1000000)	Math(수학)

$길이 N 인 양의 정수열 A_{1}, \dots, A_{N} 이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 A_{1}, \dots, A_{N} 이 오름차순이라는 것은, \forall i (1 \leq i \leq N - 1) 에 대해 A_{i} \leq A_{i + 1} 이라는 것이다.$ $수열 A 를 오름차순으로 만들기 위해, 수열 A 에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.$ $• 어떤 i (1 \leq i \leq N) 에 대해 A_{i} 에 2를 곱한다.$ $연산을 최소 횟수로 적용해서 A 를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.$

저는 처음 접근할 때, 범위를 제대로 보지 않고서 접근하다가 아예 이분탐색을 돌려버렸습니다. 그러다가 진짜 왜 틀린지 모르고 있다가 범위를 알고나서 부터 이분 탐색이라는 방법말고 다른 방법을 떠오르게 되었어요.

이제 그 아이디어에 대해서 말해보겠습니다.

일단 정의부터 시작하여 아이디어의 기초적인 기반을 다져봅시다.
$Let N_{i} = A and N_{i + 1} = B$
-> then $N_{i} \cdot 2^{x} \leq N_{i + 1} \cdot 2^{y}$
-> $\frac{N_{i} \cdot 2^{x}}{N_{i + 1}} \leq 2^{y}$
-> $x + \log_{2} (N_{i}) - \log_{2} (N_{i + 1}) \leq y$
-> $x + \frac{\log_{2} (N_{i})}{\log_{2} (N_{i + 1})} \leq y$
-> $y = ⌈ x + \frac{\log_{2} (N_{i})}{\log_{2} (N_{i + 1})} ⌉$

지금 여기서 ceil(올림)이 사용되는 이유는 나눴을 때, x.n(x>=0인 정수, n!=0)이 나오는 꼴이면 최소 곱을 알고 싶기 때문에 이것보다 더 크다면 우리는 x보다 크고 최대한 작은 값을 고르면 된다. 그래서 올림을 통해서 이를 해결한다.

이것을 통해서 알 수 있는 것은 이건 오류가 발생할 가능성이 존재한다는 것이다. (저는 코드짜서 넣고 그 다음에 블로그 쓰면서 생각해보니 이렇더라구요… 완벽한 코드는 아닌 것 같아 남깁니다..)

정답 코드

#include <iostream>
#include <cmath>
using namespace std;
using ll = unsigned long long;
int n;
int board[250'001];
int results[250'001];
int solution(int current){
    return max((int)(log2((double)board[current-1] / (double)board[current]) + (double)results[current - 1]), 0);//board[current-1])
}

int main(){
    // i번까지 모든 조건이 만족한다고 하면, i+1번은 i번보다 크다 2를 곱하는 과정을 반복문으로 하는 것이 아니라 바로 몇 번 곱해야 하는지 알 수 있는 방법을
    // 찾아보자 -> 그냥 수학으로 풀어야하는 거다!
    
    // N_i를 A라고 하자. N_{i+1}을 B라고 하자.
    // N_i * 2^x <= N_{i+1} * 2^y
    // (N_i*2^x)/N_{i+1} <= 2^y
    
    // 저기 y를 어떻게 내리냐 log 씌우면 될라나
    // (x + log_2(N_i)/log_2(N_{i+1}) <= y
    // 옹 나왔따! 근데 정답이 integer데 어떻게 나오냐
    // 아 그거구나
    // 그냥 올림처리하면 될라나
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) cin >> board[i];
    
    ll result = 0;
    for(int i = 1; i < n; i++) {
        results[i] = solution(i); result += results[i];
//        cout << results[i] << " ";
    }
//    cout << "\n";
    
    
    cout << result;
    return 0;
}