[백준 / Python 파이썬] 13699번 - 점화식

[Silver IV] 점화식 - 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)을 출력한다.

---

N = int(input())

DP = [1, 1]
for i in range(2, N + 1):
    answer = 0
    for j in range(i):
        answer += DP[j] * DP[(i - 1) - j]
    DP.append(answer)

print(DP[N])