[백준][C++] 9461: 파도반 수열

문제 링크: https://www.acmicpc.net/problem/9461

 

파도반 수열(Padovan sequence) 문제입니다.

나선에서 가장 긴 변의 길이가 다음 정삼각형의 한 변의 길이가 되는 식입니다. dp로 풀 수 있습니다.

\begin{align}
dp[1] &= 1
dp[2] &= 1
dp[3] &= 1
dp[4] &= 2
dp[5] &= 2
dp[i] &= dp[i-5]+dp[i-1] ~~~ (i \leq 6)
\end{align}

점화식은 위와 같습니다.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

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


const int INF = 987654321;
typedef long long ll;


ll dp[101];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	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 <= 100; ++i)
		dp[i] = dp[i - 5] + dp[i - 1];

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << dp[n] << '\n';
	}
	
	return 0;
}

bottom-up dp로 풀어봤습니다.

dp 배열에 long long 타입을 사용해야 하는 점 참고하세요.