https://www.acmicpc.net/problem/2727
2727번: 2,3 거듭제곱의 합
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 정수 N이 주어진다. (1 ≤ N < 231)
www.acmicpc.net
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\le0$이며, 위의 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();
}
}
'알고리즘' 카테고리의 다른 글
FORTRAN I Compiler's Operator-precedence parsing Algorithm (Operator ordering with string replacing) (0) | 2022.07.30 |
---|---|
[BOJ Solution] BOJ1078 - 뒤집음 (0) | 2022.06.21 |
[BOJ Solution] BOJ9556 - 수학 숙제 (0) | 2022.06.19 |