백준 13699 점화식

t=[1]*36
for i in range(1,36):
    target=0
    for j in range(i):
        target+=t[j]*t[i-(j+1)]
    t[i]=target
print(t[int(input())])

이 문제는 사실 DP로 안풀어도 구현가능해서..