[PS][BOJ/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 = [0 for _ in range(36)]

dp[0] = 1
dp[1] = 1
dp[2] = 2


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

문제 원본 & 소스코드 원본

https://www.acmicpc.net/problem/13699

13699번: 점화식

https://github.com/HwangBBang/BOJ_Work_Space/tree/main/%EB%B0%B1%EC%A4%80/Silver/13699.%E2%80%85%EC%A0%90%ED%99%94%EC%8B%9D

GitHub - HwangBBang/BOJ_Work_Space: 백준 문제의 풀이를 기록합니다

오류나 질문에 대한 문의 댓글로 남겨주세요!