[C/C++] 백준 #1646 피이보나치 트리(동적 계획법)

피이보나치 트리 문제는 일견 어려워보일 수 있지만, 조성 방법이 정해져 있기 때문에, 그것을 이용해서 푸시면 됩니다.

정답자가 현재 90명정도로 적은 편의 문제입니다.  구현 자체가 어려워서라기보다는 문제 자체가 어려워서인 듯 합니다.

 

N이 주어졌을 때, 루트는 최고층(가장 높은 레이어)에 위치하며 가장 먼 노드까지는 N-1번이면 도착하게 됩니다.  왼쪽 트리는 N-2에 대한 루트이고, 오른쪽 트리는 N-1에 대한 트리입니다.  이것을 이용하면 전체 트리에 대한 노드의 갯수 \(ft_N\)을 구할 수 있습니다.

 

\[ ft_0 = 1, ~ ft_1 = 1 \]

\[ ft_n = ft_{n-2} + ft_{n-1} + 1 \]

 

위의 점화식을 이용하면 우리는 손쉽게 노드의 갯수를 구할 수가 있습니다.

이제 이것을 이용하시면 됩니다.

 

예를 들어서 N이 3이라면 다음과 같은 그래프를 구할 수 있습니다.

N이 3일때 그래프

점화식을 통해서 우리는 1 1 3 5 ... 형태로 N이 3일때 5라는 값을 얻을 수 있는 것을 압니다.  시작점이 2이고, 도착점이 4라면, 그래프를 통해서 URL이 답임을 알 수 있습니다.  하지만, 그래프를 만들어서 처리하는 것은 무모합니다.  N이 50이라면 아주 큰 수(\(4 \times 10^{10}\))가 나오므로 그래프를 메모리한도내에서 구성하기도 힘들고, 메모리가 가능하더라도, 그 숫자만큼 처리하는 시간도 아주 오래 걸리죠.

 

시작점이 2라면, 루트를 제외하면 1이라는 값을 얻습니다.  \(ft_1\) 를 통해서 우리는 1이라는 값을 얻게 되고, 왼쪽 트리에 시작점이 위치한 것을 알게 됩니다.  그리고 왼쪽 트리의 루트를 제외하게 되면 0이 되어, 시작점까지 가는 것은 L인 것을 압니다.

 

도착점은 4이므로 루트를 제외하면 3이 됩니다. \(ft_1\)이 1이므로 도착점은 오른쪽 트리에 존재합니다.  다음 왼쪽트리 개수와 루트를 제외하면 1이 되고, \(ft_0\)의 값이 1이므로 왼쪽트리에 있는 것을 압니다.  그러면 RL을 얻게 됩니다.

 

다음으로는 공통 조상을 찾아야 합니다.   공통 조상은 둘 사이에 시작부터 해서 다른 문자가 나오는 경우입니다.  시작점은 L이고 도착점은 R이므로 공통 조상은 전체 그래프의 루트입니다.  그러면 시작점에서는 공통 조상까지 무조건 올라가면 되므로, U가 되고, 다음 도착점까지 가는 것이므로 URL이 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//    baekjoon #1646 - Fibonacci Tree
//        - by Aubrey Choi
//        - created at 2020-01-31
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>

int main()
{
    long long ft[50];
    int i, n, s, e, a[51], b[51], pa=0, pb=0;
    for(i=2,ft[0]=1,ft[1]=1;i<50;i++) ft[i]=ft[i-1]+ft[i-2]+1;
    scanf("%d%d%d",&n,&s,&e);
    for(i=n-1,s--;s && i>=0;i--,s--)
    {
        if(s>ft[i-1]) s-=ft[i-1], a[pa++]=1;
        else i--, a[pa++]=0;
    }
    for(i=n-1,e--;e && i>=0;i--,e--)
    {
        if(e>ft[i-1]) e-=ft[i-1], b[pb++]=1;
        else i--, b[pb++]=0;
    }
    for(s=0;s<pa && s<pb;s++) if(a[s]!=b[s]) break;
    for(i=s;i<pa;i++) putchar('U');
    for(i=s;i<pb;i++) putchar(b[i]?'R':'L');
    putchar('\n');
}