[BOJ 1341 // C++] 사이좋은 형제

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

 

이번에 볼 문제는 백준 1341번 문제인 사이좋은 형제이다.
문제는 아래 링크를 확인하자.

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

 

남아있는 케이크를 길이가 \(k\)인 패턴 한번의 시행으로 나누어먹으면 \(\frac{1}{2^k}\)만큼을 남기고 나머지는 합이 \(2^k-1\)인 음이 아닌 두 정수의 비율로 나누어 먹게 됨을 관찰하자. 남은 조각은 같은 패턴으로 계속 반복하여 먹게 되고 그 조각의 크기는 패턴을 반복할 수록 0에 수렴하므로, 이 문제는 주어진 분수의 분모를 (가능한 작은) \(2^k-1\)꼴로 만들어 분자의 이진수 표기에 따라 케이크를 두 사람에게 나누어 주는 것으로 해결할 수 있음을 알 수 있다.

 

구현에 따라 64비트 정수 자료형을 이용해도 오버플로우가 발생할 수 있으니 유의하자.

 

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

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

ll AA, BB;
lll A, B;
lll b = 1;
string ans;

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

	cin >> AA >> BB;
	A = AA, B = BB;
	while (b <= 9223372036854775807LL && b % B) {
		b = b * 2 + 1;
	}
	if (b > 9223372036854775807LL) {
		cout << -1;
		return 0;
	}
	A *= b / B;
	while (b) {
		if (A & 1) ans += '*';
		else ans += '-';
		A >>= 1, b >>= 1;
	}
	if (ans.length() > 60) cout << -1;
	else {
		while (!ans.empty()) {
			cout << ans.back();
			ans.pop_back();
		}
	}
}