[BOJ] 백준 #2078. 무한이진트리 (C++)

🎨 문제

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

• 알고리즘 분류: 수학, 트리
• 난이도: Silver 4

 

💬 풀이

문제의 무한이진트리의 어떤 노드 (a,b)에서
if a>b이면, (a,b)는 부모 노드의 왼쪽 자식이고,
if a<b이면, (a,b)는 부모 노드의 오른쪽 자식이다.

따라서
if a>b이면, (a,b)의 부모 노드는 (a-b, b)이고,
if a<b이면, (a,b)의 부모 노드의 (a, b-a)이다.

근데 입력값 A,B가 최대 20억까지라니..ㅋㅋ음

처음에 생각했던 방법은 단순히 입력 노드에서부터 규칙에 따라서 루트 노드까지 따라 올라가는 방법이었다.
이렇게 간단하게 생각하고 풀었을 땐 역시나 '시간 초과'. 👉🏻틀린 코드 확인

Why?

출처) https://www.youtube.com/watch?v=IKnjzmyk70U

이진트리에서 삽입,검색,삭제 등의 연산은 모두 트리의 높이가 얼마인지에 따라서 시간복잡도가 정해진다.

여기서 오른쪽 그림처럼 트리가 한쪽으로 치우친 모양의 입력값을 받는다면 (ex. A=20억, B=1) 시간초과가 나는 것이다.

 

---

 

어쨌든 그래서 다른 풀이방법을 생각해야 했는데, 도저히 안 떠올라서 결국 구글링을 해봤고, 풀이는 다음과 같다.

만약 (a,b)에서 계속 왼쪽 자식으로 k번 이동하면, a에 b를 k번 더하게 되고,

만약 (a,b)에서 계속 오른쪽 자식으로 k번 이동하면, b에 a를 k번 더하게 된다.

예를 들어 (1,2) -> (3,2) -> (5,2)=(1+2*2, 2)다.

 

따라서 자식(a,b)에서 몫 a/b과 나머지 a%b 등의 정보로 '계속 같은 방향인 부모'를 찾을 수 있다. 💡

 

참고) https://lastknight00.tistory.com/121

 

 

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

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

	//freopen("input.txt", "rt", stdin);
	int A, B;
	cin >> A >> B;
	int L = 0, R = 0;
	while (!(A == 1 && B == 1)) {
		/* A,B 중 하나가 1인 경우는 따로 처리 */
		if (A == 1) {
			R += B - 1;
			break;
		}
		else if (B == 1) {
			L += A - 1;
			break;
		}

		/* 연속으로 같은 방향 부모-자식은 한번에 처리 */
		if (A > B) {
			L += A / B;
			A = A % B;
		}
		else {
			R += B / A;
			B = B % A;
		}
	}

	cout << L << ' ' << R;

	return 0;
}