[BOJ Solution] BOJ2727 - 2,3 거듭제곱의 합

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

2727번: 2,3 거듭제곱의 합

Ad-hoc스러운 문제인 만큼, 풀이를 알면 쉬우나 풀이를 떠올리는 것이 조금 어려운 문제이다.

 

핵심 아이디어는 다음의 두 가지이다.

1. 임의의 자연수는 어떤 홀수 $x$와 어떤 정수 $k$에 대해 $2^k\times x$꼴로 표현된다. 특히, 짝수에 대해서는 $k$는 1 이상이다.

2. 3의 거듭제곱(1 포함)을 홀수에서 빼면 짝수가 된다.

 

위의 두 가지 사실을 이용하여 문제를 풀어보자.

1번에 의해 임의의 입력을 홀수로 변형할 수 있으며($N^{\prime }=N/2^k$), 홀수의 경우에는 2번에 의해 다시 짝수로 만들어줄 수 있다.($N^{\prime }=N-3^k$)

이 과정을 반복하여 문제를 해결할 때, $N$은 $2^{a_1}(3^{b_1}+2^{a_2}(3^{b_2}+...))$의 꼴로 표현된다. 모두 전개하면 $2^{a_1}{3}^{b_1}+2^{a_1+a_2}{3}^{b_2}+...$과 같이 표현된다는 사실을 알 수 있을 것이다. 이는 문제에서 요구하는 각각의 항과 동일한 꼴임을 발견할 수 있다.

이제 중요한 것은 이러한 항들이 문제 조건을 만족하는가이다. 즉, 2의 지수가 증가하는 순으로 나열했을 때 3의 지수를 감소하게끔 설정할 수 있는지가 핵심이 될 것이다.

$3^{b_i}$에 곱해진 2의 거듭제곱의 지수는 증가함이 자명하다. $a_1\le 0$이며, 위의 2번 사실에 의해 2 이상의 정수 $i$에 대해 $a_i>0$이기 때문이다. 그렇다면 $b_i$가 감소수열이기만 하면 이렇게 구한 항들은 문제의 정답에 해당할 것이다.

여기서, 우리는 $b_i$의 값을 확정하지 않았음을 상기하자. 따라서 감소수열 $b_i$를 적당히 정의하기만 하면 된다. 가장 무난하며 쉽게 찾을 수 있는 선택지는 선택할 수 있는 가장 큰 3의 거듭제곱이다. 이 정의의 경우 $b_i$가 단조감소한다는 사실은 3진법 전개를 통해 쉽게 증명할 수 있으므로 독자에게 맡긴다.

 

위와 같은 풀이를 재귀함수 내지는 반복문을 이용하여 구현하면 AC를 받을 수 있다. 아래는 이를 구현한 코드이다.

 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

void TC(){
    ll n;
    cin>>n;
    int b2=0;
    vector<int> v,w;
    while(n>0){
        while(n%2==0){
            b2++;
            n/=2;
        }
        ll r=1;
        int i;
        for(i=0;r<=n;i++,r*=3);
        r/=3;i--;
        n-=r;
        v.push_back(b2);
        w.push_back(i);
    }
    cout<<v.size()<<"\n";
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" "<<w[i]<<"\n";
    }
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    int tc;
    cin>>tc;
    while(tc--){
        TC();
    }
}