Boj 31963 c++ 두배

정올 기출 문제를 건드렸다가 큰코 다쳤다.

소요시간 2시간 30분.. 33점을 10번 넘게 맞고 결국 구글링을 했다.

수많은 시도의 흔적..

하지만 이문제를 통해 깨달은 점은 있다. 

그리디는 상황에 따라서 항상 최적을 추구하는 성질일 뿐이지, 그 방법은 스스로 찾아내야 한다는 것.

그리고 내가 작성한 코드가 왜 최적해를 만족시키는지 마땅한 증거가 필요하다는 것. 그리고 그리디는 브루트포스가 아니기에 시간제한을 만족할 수 있도록 코드의 시간 복잡도를 최소한으로 낮춰야 한다는 것.

 

그리고 마지막으로 깨달은 점 한가지.. '문제에서 주어진 예제가 전부가 아니라는 것' 계산 결과가 10^18을 넘어서서 오버플로우가 나는 경우까지 생각을 해주어야 했던 것이다.

 

즉, 2의 거듭제곱에 대해 다루는 이 문제에서 우리가 구해야 하는 것은 곱셈의 횟수 뿐이기에 로그를 사용할 필요가 있다.

물론 초등부, 증등부 출제 범위이기 때문에 dp로 비율을 저장하여 풀이하는 방법도 있긴하다. 하지만 아직 다이나믹 프로그래밍을 익히지 못한 입장에서 이 풀이는 조금더 실력을 연마한 후에 도전해보도록 하겠다.

 

제출한 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

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

   int N;
   long long ans=0;

   int dp[1000001];
   cin>>N;

   vector<long long> v(N);

   for(int i=0; i<N; i++){
    cin>>v[i];

   }
     for (int i = 1 ; i < N ; ++i) {
        dp[i] = (((int)ceil(log2((double)v[i - 1]/v[i]) + (double)dp[i - 1])>0) ? (int)ceil(log2((double)v[i - 1]/v[i]) + (double)dp[i - 1]) : 0);
        
        ans += dp[i];
    }
  cout<<ans;





}

dp 벡터에는 수열의 각 항에 2를 곱한 횟수를 저장해두었다. 그리고 우리가 필요한 것은 오름차순 정렬이기 때문에, 앞의 항을 뒤의 항으로 나눈 비율에 추가로 log2의 연산을 하여, 두번째 항에 2를 최소 몇번을 곱해야만 첫번째 항보다 크거나 같아지는지 구하였다. 또한 첫번째 항에서 이전 항으로 인해 곱해지는 연산을 고려하여 이전 항의 곱셈 횟수 또한 더해주었다. 이는 앞의 수에 2가 특정 횟수 곱해졌을 시에 그 곱셈을 상쇄시키기 위한 연산이다. log부등식으로 이해하면 편하다.

수식은 지피티로 만들었다.

이렇게 하면 dp[i], 즉 i번째 항에 2를 곱해야 할 최소 횟수를 구할 수 있다. 하지만 우변이 0, 또는 음수가 된다면 연산은 할 필요가 없기에 dp[i]에는 0이 저장된다. i번째 항은 이미 연산을 마친 i-1번째 항보다도 크기 때문이다. 즉, 이전 항에 2를 연산한 횟수를 기억해가며, 이를 적용한 후의 값에 대해서 이후 항에 2를 곱해야 하는 최소 횟수를 구하는 것이다. 이는 항상 최적해를 찾아나가는 그리디 알고리즘의 논리와도 상통한다.

 앞으로는 더 많은 문제를 자력으로 풀어내기 위해 노력하겠다.