백준 9461 - 파도반 수열

아래 사진과 같이 삼각형이 마치 피보나치 수열처럼 수가 늘어날 때 n번째 수를 구하는 문제입니다.

6번째 삼각형을 예시로 보면 맞닿아있는 면이 첫번째 삼각형과 4번째 삼각형입니다.

그 이후 삼각형들도 맞닿아있는 면을 보면 이전 삼각형과 5번째 전 삼각형임을 확인할 수 있습니다.

순서	값	식
1	1
2	1
3	1
4	2
5	2
6	3	tris[n-1] + tris[n-5] (5 + 1)
7	4	tris[n-1] + tris[n-5] (6 + 2)
8	5	tris[n-1] + tris[n-5] (7 + 3)
9	7	tris[n-1] + tris[n-5] (8 + 4)
10	9	tris[n-1] + tris[n-5] (9 + 5)
11	12	tris[n-1] + tris[n-5] (10 + 6)
12	16	tris[n-1] + tris[n-5] (11 + 7)

이를 통해 5 이후의 수열은 점화식을 통해 값을 알아낼 수 있습니다.

#include <iostream>
#include <vector>

int main()
{
	int testCnt;
	std::cin >> testCnt;

	std::vector<long long> tris(101);

	tris[1] = 1;
	tris[2] = 1;
	tris[3] = 1;
	tris[4] = 2;
	tris[5] = 2;

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

	for (int t = 0; t < testCnt; t++)
	{
		int num;
		std::cin >> num;

		std::cout << tris[num] << "\n";
	}

	return 0;
}

---

이외에도 다른 방식으로 점화식을 구할 수 있습니다. 이 글에서는 4번째 삼각형부터 적용 가능하기에 더 일반적이라고 볼 수 있습니다.