[BOJ 17167] A Plus Equals B

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

17167번: A Plus Equals B

 

- 문제 요약

 

두 정수 A와 B가 입력으로 주어집니다.A와 B를 똑같이 만들어야 하며, 만드는 과정 중에는 아래의 4가지 연산을 사용할 수 있습니다.

• A+=A
• A+=B
• B+=A
• B+=B

위 연산은 최대 5000번까지 수행할 수 있습니다. 이때 필요한 횟수와 그 방법을 출력하세요.

 

 

- 알고리즘 정리

 

a+=a는 a*2와 같고, b+=b는 b*2와 같습니다.

이런 경우에 둘 중 하나가 2의 배수라면 그 수를 /2 하는 것과 같습니다.

둘 다 %2==1 이라면 이는 홀수라는 것이고, a+=b 또는 b+=a 연산을 해서 둘 중 하나를 짝수로 만들어줘야 합니다.

이런 흐름으로 계속 연산을 진행하다 보면 문제를 해결할 수 있습니다.

 

 

- 코드 작성

 

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

#define MAX 1000001
typedef long long ll;
ll a,b,c,num,arr[MAX],brr[MAX];

int gcd(ll x, ll y){
    if(y==0){
        return x;
    }
	else{
        return gcd(y,x%y);
    }
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>a>>b;
	c=gcd(a,b);
	a/=c;
	b/=c;
	while(a!=1||b!=1){
		while(a%2==0LL){
			num++;
			arr[num]=2;
			brr[num]=2;
			a/=2;
		}
		while(b%2==0LL){
            num++;
            arr[num]=1;
            brr[num]=1;
            b/=2;
        }
		if(a<b){
			num++;
			arr[num]=2;
			brr[num]=1;
			num++;
			arr[num]=1;
			brr[num]=1;
			b=(a+b)/2;
		}
		if(b<a){
			num++;
			arr[num]=1;
			brr[num]=2;
			num++;
			arr[num]=2;
			brr[num]=2;
			a=(a+b)/2;
		}
		c=gcd(a,b);
		a/=c;
		b/=c;
	}
	cout<<num<<'\n';
	for(int i=1;i<=num;i++){
        if(arr[i]==1){
        	cout<<"A";
		}
		if(arr[i]==2){
			cout<<"B";
		}
		cout<<"+=";
		if(brr[i]==1){
			cout<<"A\n";
		}
		if(brr[i]==2){
			cout<<"B\n";
		}
	}
}

코드 제출 결과