문제

다음 점화식에 의해 정의된 수열 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
  일 때 주어진 n에 대해 t(n)값을 출력하면 된다.

코드

n = int(input())
ans= list()

for i in range(n+1):
    tmp = 0
    for j in range(i):
        tmp += ans[j]*ans[i-1-j]
    if i == 0:
        ans.append(1)
    else:
        ans.append(tmp)


print(ans[-1])

설명

피보나치 수열의 변형문제이다. 재귀로 풀려고 했으나 잘 생각이 나지 않아서 반복문으로 해결했다. 예시로 주어진 수열을 보면 n-1번 만큼의 덧셈이 일어나고 곱셈이 이루어지는 항을 보면 한쪽이 증가하면 한쪽이 감소한다는 것을 보면 규칙성을 알아낼 수 있다.