[🥈4 / 백준 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 ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

입력

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

출력

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

 

예제 입력 1 3	예제 출력 1 5
예제 입력 2  25	예제 출력 2  4861946401452

 

풀이

 

점화식을 통해 t(n)을 구하는 문제이다.

 

이미 문제에 점화식이 나와 있으므로, 구현만 잘 한다면 크게 어렵지 않은 문제이다.

t(n)을 구하기 위해 t(0), t(1), …, t(n-1) 이 필요하므로 메모이제이션을 활용해야 한다.

 

t(0)과 t(1)만 미리 dp 배열에 넣어놓고 나머지를 n까지 쭉 생성하는 방식으로 코드를 작성했다.

 

n = int(input())
dp = [1,1]

while(n+1 > len(dp)):
    r = 0
    for i in range(len(dp)):
        r += dp[i]*dp[len(dp)-i-1]
    dp.append(r)
print(dp[n])