BOJ #13699

문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

• t(0)=1
• t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

이 정의에 따르면,

• t(1)=t(0)*t(0)=1
• t(2)=t(0)*t(1)+t(1)*t(0)=2
• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
• ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

풀이

크게 어려운 문제가 아니죠. 문제에서 나온대로 0번째 항을 정의해 준 다음, 점화식에 따라 35번째 항까지 배열을 사용해 채워넣습니다. 그런다음 n을 입력받은 다음 배열의 n번째 인덱스를 출력하면 끝입니다. 이미 만들어진 배열에서 값을 가져오기 때문에 시간복잡도는 O(1) 입니다.

사용한 언어 & 컴파일 환경

C14@Visual Studio 2015

소스코드

#include <stdio.h>
int main()
{
    unsigned long long int arr[36] = { 0 }, tmp=0;
    int i, n;
 
    arr[0] = 1;
    for (i = 1; i < 36; i++)
    {
        for (n = 0; n < i; n++)
            tmp += (arr[n] * arr[i - n - 1]);
        arr[i] += tmp;
        tmp = 0;
    }
 
    int N;
    scanf("%d", &N);
    printf("%lld", arr[N]);
}