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

 

이번에 볼 문제는 백준 1646번 문제인 피이보나치 트리이다.
문제는 아래 링크를 확인하자.

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

 

1646번: 피이보나치 트리

첫째 줄에 N과 시작 위치와 도착 위치가 공백을 사이에 두고 주어진다. N은 50보다 작거나 같은 자연수 또는 0이다. 시작 위치와 도착 위치는 1,000,000,000보다 작거나 같으며, N번째 피이보나치 트리

www.acmicpc.net

먼저, N 이하의 각 피이보나치 트리들을 구성하는 노드의 개수를 미리 구해두자.

 

N번째 피이보나치 트리에서, 루트로부터의 위치를 알고 싶은 노드를 x라 부르자. N번째 피이보나치 트리의 루트에서 x까지의 최단경로는 x의 왼쪽 서브트리와 오른쪽 서브트리의 크기와 x의 대소비교를 통해 구할 수 있다.

 

구체적으로 현재 살펴보고 있는 피이보나치 트리를 n번이라 할 때, x가 1이라면 "현재 살펴보는 피이보나치트리"의 루트가 목적지이므로 경로 탐색을 마친다. 그렇지 않은 경우 x가 왼쪽 서브트리에 들어있을지 오른쪽 서브트리에 들어있을지를 판단한다. x가 왼쪽 서브트리에 들어있다면 (x-1)은 (n-2)번 피이보나치트리의 노드수 이하여야 한다. x가 왼쪽 서브트리에 들어있지 않다면, (x-1)에서 왼쪽 서브트리에 들어있는 노드 수를 뺀 만큼의 노드 수를 가지고 오른쪽 서브트리로 탐색을 이어나간다.

 

문제에서 주어지는 시작 위치와 도착 위치에 대하여 위와 같은 경로를 각각 구해내면 시작 위치에서 (시작 위치와 도착 위치의 LCA)까지 U를, (시작 위치와 도착 위치의 LCA)에서 도착위치까지 도착위치의 경로를 이용하여 문제를 해결할 수 있다.

 

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

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

ll arr[51];
string s1, s2;
int s1len, s2len;

void func(int idx, ll val, string& s) {
	if (val == 1) return;
	val--;
	if (arr[idx - 2] >= val) {
		s += 'L';
		func(idx - 2, val, s);
	}
	else {
		s += 'R';
		func(idx - 1, val - arr[idx - 2], s);
	}
}

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

	arr[0] = arr[1] = 1;
	int N; cin >> N;
	for (int i = 2; i <= N; i++) arr[i] = arr[i - 1] + arr[i - 2] + 1;

	ll x, y; cin >> x >> y;
	if (x == y) return 0;

	func(N, x, s1);
	func(N, y, s2);

	s1len = s1.length(), s2len = s2.length();
	if (s1len < s2len) {
		if (s1 == s2.substr(0, s1len)) {
			for (int i = s1len; i < s2len; i++) cout << s2[i];
			return 0;
		}
	}
	else if (s1len > s2len) {
		if (s2 == s1.substr(0, s2len)) {
			for (int i = s2len; i < s1len; i++) cout << 'U';
			return 0;
		}
	}

	int idx = 0;
	while (s1[idx] == s2[idx]) idx++;
	for (int i = idx; i < s1len; i++) cout << 'U';
	for (int i = idx; i < s2len; i++) cout << s2[i];
}
728x90

'BOJ' 카테고리의 다른 글

[BOJ 17773 // C++] Fortune Telling  (0) 2022.07.09
[BOJ 1637 // C++] 날카로운 눈  (0) 2022.07.08
[BOJ 2041 // C++] 숫자채우기  (0) 2022.07.06
[BOJ 11058 // C++] 크리보드  (0) 2022.07.05
[BOJ 5052 // C++] 전화번호 목록  (0) 2022.07.04

+ Recent posts