[Silver 3] 9461번 파도반 수열

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

9461번: 파도반 수열

 

이 문제는 DP를 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

수의 변화는 전 요소와 5번째 전 요소를 합한 값과 같다. 

이는 6번째 요소부터 규칙을 가지기 때문에 이를 코드로 변화시키면 된다.

 

#include <iostream>
#include <string>
using namespace std;

int N;
long long dp[101];

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		dp[1] = 1;
		dp[2] = 1;
		dp[3] = 1;
		dp[4] = 2;
		dp[5] = 2;
		for (int i = 6; i <= N; i++) {
			dp[i] = dp[i - 1] + dp[i - 5];
		}

		cout << dp[N] << '\n';
	}
}