[BOJ 17167 // C++] A Plus Equals B

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17167번 문제인 A Plus Equals B이다.
문제는 아래 링크를 확인하자.

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

17167번: A Plus Equals B

두 수 A와 B가 주어졌을 때, A+=A, A+=B, B+=A, B+=B 네 가지 연산만을 가지고 A와 B를 같게 만드는 방법을 찾는 문제이다.

 

서브태스크1) A=1인 경우

A에 A+=A 연산만을 반복하여 적용한다면 A는 2의 거듭제곱 꼴의 수를 계속 나타낼 것이라는 것을 관찰하자.

이를 이용하여, A에 A+=A만을 반복해가면서 B에 적절하게 B+=A 연산을 적용하여 B를 2의 거듭제곱꼴로 만들어준다면 A와 B는 하나의 2의 거듭제곱꼴로 서로 같아지게 될 것이다.

 

서브태스크2) (제약없음)

만약 두 수중 하나를 위의 1과 같은 취급을 할 수 있는 수로 바꿀 수 있다면(다른 수의 약수가 될 수 있게 바꿀 수 있다면) 서브태스크1의 결과를 그대로 사용하여 문제를 마무리지을 수 있을 것이다.

다음과 같은 연산을 반복하여 두 수의 크기를 줄여나가자.

 

0) A=1, B=1, 또는 A=B라면 반복을 종료한다.

1) A와 B가 모두 홀수이면 둘 중 큰 수에 작은 수를 더해준다.

2) A가 홀수이면 A+=A를 한다.

3) B가 홀수이면 B+=B를 한다.

4) A와 B가 모두 짝수이면 두 수를 각각 2로 나누어 저장한다. 이렇게 저장하여도 최종적인 답이 변하지 않는다는 점을 확인하자.

 

2) 또는 3)의 다음 차례에는 항상 4)가 오므로, 저장된 A와 B의 곱은 두 과정으로 절반이 된다는 점을 확인하자.

또한, 1)을 한다면 다음 차례에는 2) 또는 3)이 이어지므로 저장된 A와 B의 곱이 작아진다는 점을 확인하자. (A=B인 경우는 0번 과정에서 제외되었다는 점과, 작은 수를 큰 수에 더했다는 점을 눈여겨보자.)

 

따라서 위와 같은 과정을 반복하면 유한번의 연산으로 (저장된 A와 B가) A=1, B=1 또는 A=B인 두 수 A와 B를 얻어낼 수 있다.

 

남은 일은 서브태스크1의 과정을 이용하여 A와 B를 같게 만드는 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;

vector<int> ans;
string s[4] = { "A+=A\n", "A+=B\n", "B+=A\n", "B+=B\n" };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll A, B; cin >> A >> B;

	while (A > 1 && B > 1 && A != B) {
		if (A & 1 && B & 1) {
			if (A > B) {
				A += B;
				ans.emplace_back(1);
			}
			else {
				B += A;
				ans.emplace_back(2);
			}
		}
		else if (A & 1) {
			A += A;
			ans.emplace_back(0);
		}
		else if (B & 1) {
			B += B;
			ans.emplace_back(3);
		}
		else {
			A >>= 1, B >>= 1;
		}
	}
	
	if (A != B) {
		if (A == 1) {
			while (A < B) {
				if (B & 1) {
					B++;
					ans.emplace_back(2);
				}
				ans.emplace_back(0);
				B >>= 1;
			}
		}
		else {
			while (B < A) {
				if (A & 1) {
					A++;
					ans.emplace_back(1);
				}
				ans.emplace_back(3);
				A >>= 1;
			}
		}
	}

	cout << ans.size() << '\n';

	for (auto x : ans) cout << s[x];
}