[백준 9461] 파도반 수열

대놓고 점화식 세우라고 힌트 준 DP문제이다.

한 삼각형의 변이 어떤 규칙에 의해 정해지는지 확인해보자.

1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 9

이 문제를 해결할 때, 난 6번째 삼각형부터 확실한 규칙이 보였다.

6번째부터 파란색 삼각형의 한 변의 길이는 두 개의 흰색 삼각형 변의 길이의 합이고, 흰색 삼각형의 한변의 길이는 두 개의 파란색 변의 길이의 합인 것을 봤다.

 

다시 눈을 크게 뜨고 보자.

삼각형의 변의 길이를 결정하는 두 개의 삼각형 중 하나는 무조건 바로 전에 만들어진 삼각형이고, 다른 하나는 5번째 전에 만들어진 삼각형이다.

 

결국 점화식은 \(a_n = a_{n-1} + a_{n-5}\) 이 된다. 

코딩 하자 !

아 참.. 이 문제는 n이 100까지라 int형 범위를 초과할 수 있다.

사실 나도 배열을 int형으로 선언하고 틀렸습니다를 받은 다음에 범위를 초과할 수 있다는 것을 캐치했다.

그러니.. 배열을 long long 타입으로 선언하자.

#include <bits/stdc++.h>
using namespace std;

long long dp[101];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	dp[1] = 1;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 2;

	for (int i = 6; i < 101; i++) dp[i] = (dp[i - 1] + dp[i - 5]);

	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		cout << dp[n] << '\n';
	}


	return 0;
}