[BAE/<JOON> 문제풀이] 1646. 피이보나치 트리

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

1646번: 피이보나치 트리

서론

구현 연습하자. 경로 구현하는데 너무 헷갈렸다. 태그는 못봤는데 LCA 문젠 것 같다.

---

풀이

최소 공통 조상을 구하고 출발 정점 s 로부터의 경로와 도착 정점 e까지의 경로를 차례대로 출력하면 된다. ( 전부 U일 수 밖에 없다. )

그리고 한가지 주의할 점은 n=50 까지 진행했을 때 트리 정점 개수가 상당히 많으므로 미리 정점 번호를 계산해서 s 나 e 가 없는 쪽 자식은 탐색을 시작하지 않아야 한다.

현재 정점 번호를 root 라고 하고 arr[si]를 현재 n 크기라고 할 때 양쪽 자식의 정점 번호 범위는 아래와 같다.

• 왼쪽 자식 시작 : root + 1
• 왼쪽 자식 끝 : root + arr[si - 2]
• 오른쪽 자식 시작 : root + arr[si - 2] + 1
• 오른쪽 자식 끝 : root + arr[si] - 1

경로는 못찾은 상태를 정의해놓고 찾았을 경우 빈 문자열을 초기화해서 호출자로 리턴할 때마다 L/R/U 를 추가해가며 만들었다. 최종적으로 최소 공통 조상 노드에서 만났을 때 경로 문자열을 출력하고 exit(0) 코드를 호출해 프로그램을 종료한다.

---

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> arr(51);
ll n, s, e;
struct pt {
    string s, e;
};
pt r(ll root, ll si) {
    if (arr[si] == 1) {
        if (root == s) {
            return { "", "NO" };
        }
        if (root == e) {
            return { "NO", "" };
        }
        return { "NO", "NO" };
    }
    pt lr = { "NO", "NO" }, rr = { "NO", "NO" };    
    ll ls = root + 1;
    ll le = root + arr[si - 2];
    string st = "NO";
    string et = "NO";
    if ((ls <= s && s <= le) || (ls <= e && e <= le)) {
        lr = r(ls, si - 2);
        if (lr.s != "NO") {
            lr.s = 'U' + lr.s;
        }        
        if (lr.e != "NO") {
            lr.e = 'L' + lr.e;
        }       
    }
    ll rs = arr[si - 2] + root + 1;
    ll re = arr[si] + root - 1;
    if ((rs <= s && s <= re) || (rs <= e && e <= re)) {
        rr = r(rs, si - 1);       
        if (rr.s != "NO") {
            rr.s = 'U' + rr.s;
        }        
        if (rr.e != "NO") {
            rr.e = 'R' + rr.e;
        }
    }
    if (root == s) {
        lr.s = "";
        rr.s = "";
    }
    if (root == e) {
        lr.e = "";
        rr.e = "";
    }
    if (lr.s != "NO") {
        st = lr.s;
    }
    if (lr.e != "NO") {
        et = lr.e;
    }
    if (rr.s != "NO") {
        st = rr.s;
    }
    if (rr.e != "NO") {
        et = rr.e;
    }
    if (st != "NO" && et != "NO") {
        cout << st << et;
        exit(0);
    }    
    return { st, et };
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    arr[0] = 1;
    arr[1] = 1; 
    for (int i = 2; i <= 50; i++) {
        arr[i] = arr[i - 1] + arr[i - 2] + 1;
    }
    cin >> n >> s >> e;    
    if (s == e) {
        return 0;
    }
    pt ret = r(1, n);
    cout << ret.s << ret.e;    
    return 0;
}