동캄의 코딩도장

백준 13699 [점화식] 파이썬 본문

코테/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를 이용하여 값을 계산하는 간단한 문제이다.

'코테 > BOJ' 카테고리의 다른 글

백준 15652 [N과M (4)] 파이썬  (0) 2021.12.02
백준 15651 [N과M (3)] 파이썬  (0) 2021.12.02
백준 15650 [N과M (2)] 파이썬  (0) 2021.12.02
백준 15649 [N과M (1)] 파이썬  (0) 2021.12.02
백준 14606 [피자 (Small)] 파이썬  (0) 2021.12.01
'코테/BOJ' Related Articles more