[백준/Python] 13699_점화식

문제 출처 : https://www.acmicpc.net/problem/13699

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

www.acmicpc.net](https://www.acmicpc.net/problem/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)을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

출력

첫째 줄에 t(n)을 출력한다.

---

풀이

import sys

n = int(sys.stdin.readline())

t = [0 for _ in range(36)]
t[0] = 1
t[1] = 1

for i in range(2,n+1):
    for j in range(i):
        t[i] += t[j] * t[i-1-j]

print(t[n])

문제 정의에 따르면 n이 0,1 일때는 t[n]의 값은 1이므로, 우선 초기화 시켜준다.

이후 주어진 입력값 n에 대하여, t[n] 까지 bottom-up 방식으로 주어진 점화식을 이용하여 차근차근 구해준다.

최종적으로 n번째 값인 t[n]을 출력해준다.