코테/BOJ

백준 13699 [점화식] 파이썬

동 캄 2021. 12. 1. 23:45
반응형

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

#13699
n=int(input())

dp=[0]*(n+1)
dp[0]=1

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

DP를 이용하여 값을 계산하는 간단한 문제이다.

반응형