Koala - 6기/코딩테스트 준비 스터디

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

Juno7 2022. 3. 20. 00:42

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

 

문제분석

점화식 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]을 출력하면 답이 나오게 된다.