취미로 코딩하기

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

이번에 볼 문제는 백준 2078번 문제인 무한이진트리이다.
문제는 아래 링크를 확인하자.

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

각 순서쌍 (A,B)를 잘 살펴보자. (A,B)가 (1,1)이 아니라면, 이전 단계를 (p,q)라 할 때 (A,B)는 (p+q,q) 또는 (p,p+q)의 형태로 나타나게 된다. 즉 A와 B는 (1,1)을 제외하면 서로 같을 수 없다. 따라서, (1,1)이 아닌 (A,B)는 항상 A>B 또는 A<B이다.

이 때, A>B라면 이전 단계 (p,q)에서 다음 단계로의 진행은 (p+q,q)일 수밖에 없고, A<B라면 이전 단계 (p,q)에서 다음 단계로의 진행은 (p,p+q)일 수밖에 없다. 다른 진행을 택하면 A와 B의 대소관계를 만족시킬 수 없기 때문이다.

위의 진행방향을 살폈을 때 결국 (A,B)의 이전 단계는 유일하게 존재할 수밖에 없음을 알 수 있고, 그 이전 단계는 A>B라면 (A-B,B), A<B라면 (A,B-A)임을 알 수 있다.

위의 진행은 유클리드 알고리즘과 거의 같으므로, 그 해결방식을 따와 문제를 해결하자. 단, 유클리드 알고리즘은 한쪽이 0이 될 때까지 진행하므로, 마지막 스텝에서 1을 빼는 단계를 하나 다시 돌려놓아야 한다는 점을 잊지 말자.

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

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> func(int A, int B) {
	if (A == 0) return make_pair(-1, 0);
	if (B == 0) return make_pair(0, -1);

	if (A > B) {
		auto p = func(A % B, B);
		return make_pair(p.first + A / B, p.second);
	}
	else {
		auto p = func(A, B % A);
		return make_pair(p.first, p.second + B / A);
	}
}

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

	int A, B; cin >> A >> B;
	auto p = func(A, B);
	cout << p.first << ' ' << p.second;
}