[python] 백준 13699번 점화식

문제 풀이

문제를 가만히 보면 규칙이 있다는 걸 알 수 있다.

그림을 보면 반복문이 쓰인다는 것을 알아챌 수 있다.

 

n의 범위가 0 ≤ n ≤ 35 이므로 미리 t(0)부터 t(35)까지의 값들을 구한다.

다 구하는 이유는 예를 들어 t(0)과 t(1)의 값만 있다고 생각하면 t(3)을 구하기 위해서는 t(2)의 값을 알아야 하는데 t(2)의 값이 구해지지 않았기 때문에 일단 미리 순차적으로 t(0)부터 t(35)까지의 값들을 다 구해놓은 후 입력값이 어떤 숫자(n)가 들어왔는지에 따라 해당 t(n)을 반환해주면 된다.

 

글이 이해가 안된다면 그림을 보면 좀 더 이해하기 쉬울 것이다.

완성된 코드!!👍😊

n = int(input())
# t(0) = 1
t = [1]
# n의 범위가 0부터 35까지이나 t(0)은 이미 값이 있으므로 제외 1~35까지만 구하면됨
for val in range(1, 36):
    j = val - 1
    tot = 0
    for i in range(val):
        tot += (t[i] * t[j])
        j -= 1
    t.append(tot)

print(t[n])