cho.sh

점화식

t(n)을 t(0)t(n-1) + t(1)t(n-2) + ... + t(n-1)t(0)으로 정의할 때, n이 35 이하로 주어지면 t(n)을 출력한다.

쉬움3동적 계획법수학조합론구현면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

다음 점화식으로 정의된 수열 t(n)t(n)을 생각하자.

  • t(0)=1t(0) = 1
  • t(n)=t(0)t(n−1)+t(1)t(n−2)+⋯+t(n−1)t(0)t(n) = t(0)t(n-1) + t(1)t(n-2) + \cdots + t(n-1)t(0) (n≥1n \ge 1)

정의를 그대로 적용하면 t(1)=t(0)t(0)=1t(1) = t(0)t(0) = 1, t(2)=t(0)t(1)+t(1)t(0)=2t(2) = t(0)t(1) + t(1)t(0) = 2, t(3)=t(0)t(2)+t(1)t(1)+t(2)t(0)=5t(3) = t(0)t(2) + t(1)t(1) + t(2)t(0) = 5이다.

정수 nn이 주어지면 t(n)t(n)을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 nn이 주어진다. (0≤n≤350 \le n \le 35)

출력

첫째 줄에 t(n)t(n)을 출력한다. t(35)t(35)까지의 값은 모두 부호 있는 64비트 정수 범위에 들어간다.