[백준 / python] 13699번: 점화식

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

13699번: 점화식

 

문제분석

점화식 t(n)이 주어지고 정수를 입력받아 점화식에 해당하는 정수를 대입했을 때의 값을 출력하는 되는 문제이다. 문제에 t(0), t(1), t(2), t(3)이 주어져 있으므로 이를 이용하여 점화식을 만들면 된다.

 

코드

n = int(input())
t = [0 for _ in range(36)]
t[0] = 1
t[1] = 1
t[2] = 2
t[3] = 5

if n>3:
    for i in range(4,n+1):
        for j in range(i):
            t[i] += t[j]*t[i-j-1]

print(t[n])

 

문제풀이

문제에 나온 점화식을 이중 for문으로 만들면 풀 수 있는 문제이다. 문제에서 주어져 있는 t(0), t(1), t(2), t(3)을 활용하여 이중 for문을 만들고 만약 입력된 값이 3보다 클 경우, 이 이중 for문을 돌면서 점화식에 의해 리스트가 채워지게 된다. 입력된 n에 따라 2중 for문을 돌게 되면서 리스트가 n만큼 채워지게 되고 마지막으로 t[n]을 출력하면 답이 나오게 된다.