백준 9461 - 파도반 수열

문제 번호: 9461

문제 제목: 파도반 수열

문제 주소: https://www.acmicpc.net/problem/9461

문제 내용

위 이미지와 같이 P(N)의 값이 증가한다고 할 때 P(N)의 값을 출력한다.
P(N)의 값은 1 1 1 2 2 3 4 7 9 12 ... 순서로 증가한다.

테스트 케이스

5 1 5 6 12 100

1 2 3 16 888855064897

문제 풀이

위 이미지에서 색칠이 된 선분을 보면 직전 삼각형과 5번째 이전 삼각형의 변 길이의 합이라는 것을 알 수 있다.
즉, f(n) = f(n - 1) + f(n - 5)라는 규칙을 갖는다.
점화식으로 [0] ~ [4]까지 1, 1, 1, 2, 2를 넣어주고 [5] ~ [100]까지 수열을 구해준 이후 테스트 케이스에 해당하는 결과값을 출력해주면 된다.
결과 값이 최대 88억까지 나올 수 있으므로 수열의 기본 자료형은 64bit 이상으로 하여야 한다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_9461()
{
	int T;
	cin >> T;
	uint64_t sequence[100] = { 1, 1, 1, 2, 2, };
	for (int i = 5; i < 100; ++i)
	{
		sequence[i] = sequence[i - 1] + sequence[i - 5];
	}
	for (int i = 0; i < T; ++i)
	{
		int pn;
		cin >> pn;
		cout << sequence[pn - 1] << "\n";
	}
	return;
}