BOJ 17167 - A plus Equals B

문제 링크 : https://www.acmicpc.net/problem/17167

문제 설명

두 숫자 a,b 가 주어져 있을 때, 5000번 이하의 a+=b, a+=a, b+=b, b+=a의 4가지 행동을 통해서 a와 b를 똑같게 만들 것이다. 이때 걸리는 횟수와 그 방법을 출력하시오. 

문제 풀이

일단 범위를 줄이는 데 집중을 해보자. 3,9로 수를 시작하는 것과, 1,3으로 수를 시작하는 것은 다른 결과가 나올까? 라는 질문으로 시작을 하게 되면 아니라는 결론이 나오게 된다. 좀 더 확장시켜서 생각을 해보면 항상 a,b를 같게 만드는 일련의 행동들은 c=gcd(a,b)인 c에 대해서 a/c, b/c를 같게 만들 수 있다. 물론 반대도 성립한다. 

a+=a는 a를 두 배 시키는 것과 동치이다. 따라서 b가 2의 배수이면 b를 절반으로 깍는 것과 동치이다. 따라서 결국 계속 절반으로 깎아서 log 정도의 스케일로 같이 만드는 방향으로 잡 이는 b에 대해서도 동일하게 성립한다. 

만약 둘 다 절반으로 깎을 수 없다는 것은 둘 다 홀수라는 것이다. 이때는 a+=b 또는 b+=a를 통해서 둘 중 하나를 짝수로 만들 수 있다. 그 다음 결국 절반으로 줄일 것이기 때문에 예를 들어서 a+=b -> a/=2 를 하게 된다면 결국 a=(a+b)/2로 바꾼다는 것이다. 즉, 둘의 절반 지점으로 숫자 하나를 이동시키는 것이다. 따라서 약 $O(lg(a-b))$의 시간 복잡도에 문제를 해결할 수 있다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll arr[1010101];
ll brr[1010101];
 
int main(){
    ll a,b,cnt=0,i;
    scanf("%lld %lld",&a,&b);
    ll c=__gcd(a,b);
    b/=c; a/=c;
    while(a!=1||b!=1){
        while(a%2==(ll)0){
            cnt++;
            arr[cnt]=2;
            brr[cnt]=2;
            a/=2;
        }
        while(b%2==(ll)0){
            cnt++;
            arr[cnt]=1;
            brr[cnt]=1;
            b/=2;
        }
        if(a<b){
            cnt++;
            arr[cnt]=2;
            brr[cnt]=1;
            cnt++;
            arr[cnt]=1;
            brr[cnt]=1;
            b=(a+b)/2;
        }
        if(b<a){
            cnt++;
            arr[cnt]=1;
            brr[cnt]=2;
            cnt++;
            arr[cnt]=2;
            brr[cnt]=2;
            a=(a+b)/2;
        }
        ll c=__gcd(a,b);
        b/=c; a/=c;
    }
    
    printf("%lld\n",cnt);
 
    for(i=1;i<=cnt;i++){
        if(arr[i]==1) printf("A");
        if(arr[i]==2) printf("B");
        printf("+=");
        if(brr[i]==1) printf("A\n");
        if(brr[i]==2) printf("B\n");
    }
}