BOJ [9461] 파도반 수열

https://www.acmicpc.net/problem/9461

1. 분류

다이나믹 프로그래밍

2. 풀이

첫 몇 항을 제외한 나머지 모두가 규칙에 맞춰 증가하는 형태를 이루고 있다.

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

3이 쓰여진 삼각형의 한쪽 변에 1, 2 삼각형,

4가 쓰여진 삼각형의 한쪽 변에 1, 3 삼각형,

5가 쓰여진 삼각형의 한쪽 변에 1, 4 삼각형, ...

D[N] = D[N-1] + D[N-5]의 규칙에 맞춰서 증가한다.

첫 몇 항만 초기화해주고 나머지는 저대로 구하면 답을 쉽게 찾아낼 수 있다.

3. 소스코드

#include <cstdio>
unsigned long long d[100];

int main()
{
	int t;
	scanf("%d", &t);

	d[0] = d[1] = d[2] = 1;
	d[3] = d[4] = 2;

	for (int i = 5; i < 100; i++)
		d[i] = d[i - 1] + d[i - 5];

	while (t--)
	{
		int n;
		scanf("%d", &n);

		printf("%llu\n", d[n - 1]);
	}

	return 0;
}