백준 9461 파도반 수열

 

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

 

 

풀이

점화식을 세우는것이 중요하다.

 

n1	n2	n3	n4	n5	n6	n7	n8	n9	n10
1	1	1	2	2	3	4	5	7	9

 

n6부터 n[i] = n[i-5] + n[i-1]의 규칙을 발견할 수 있다.

즉 n6 = n1 + n5

 

 

구현

배열에 integer 범위를 초과하는 값이 들어가므로 더 큰 자료형을 선언해야한다.

// C++

#include <iostream>

using namespace std;

int t, n;
long long dp[101];

void cal() {
	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 main() {
	cal();
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		cout << dp[n] << endl;
	}

}