끄적끄적
백준 13699 [점화식] 본문
출처 : www.acmicpc.net/problem/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 ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.
출력
첫째 줄에 t(n)을 출력한다.
예제 입력 1
3
예제 출력 1
5
예제 입력 2
25
예제 출력 2
4861946401452
dp의 쉬운 축에 속하는 문제이다.
어느 인덱스가 주어지던 미리 다 계산하고 해당 인덱스를 출력하는 방식으로 구현하였다.
double로 두고 구현하면 숫자가 커질 경우 e로 표기되어 오답이 뜨기 때문에, 전체 숫자가 나오도록 long long으로 구현해야한다.
'코테준비 > 백준' 카테고리의 다른 글
백준 [14247] 나무 자르기 (0) | 2021.05.18 |
---|---|
백준 2003 [수들의 합 2] (0) | 2021.05.07 |
백준 14614 [Calculate!] (0) | 2021.05.07 |
백준 10984 [내 학점을 구해줘] (0) | 2021.05.03 |
백준 18353 [병사 배치하기] (0) | 2021.04.05 |