백준 9461 c++ "파도반 수열" -PlusUltraCode-

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

 

 

 

 

 

 

[필자 사고]

 

이 문제는 이전 값이 영향을 주는 다이나믹 프로그래밍이다.

 

오른쪽 그림을 보면서 d[11] 까지 직접 손으로 구해보면 규칙성을 금방 찾을 수 있다.

 

해당 문제의 점화식은 아래와 같다.

 

d[i] = d[i-5] + d[i-1]  단 (i>=6) 이다.

 

1~5까지의 값은 직접 입력해주고 나머지 범위들을 계산해 주면된다.

 

또한 index 100까지 가면 int의 범위가 초과되기 때문에 반드시

 

long 이상의 자료형으로 배열을 초기화 해줘야 된다.

 

 

[소스 코드]

 

#include <iostream>
#include <vector>


using namespace std;

int T;
vector<int> arr;
vector<long> Dp;

void Input() {
	cin >> T;
	Dp.resize(101);
	Dp[1] = 1;
	Dp[2] = 1;
	Dp[3] = 1;
	Dp[4] = 2;
	Dp[5] = 2;
	arr.resize(100000);
	for (int i = 0; i < T; i++) {
		cin >> arr[i];
	}
}

void Solve() {
	for (int i = 6; i <= 100; i++) {
		Dp[i] = Dp[i - 5] + Dp[i - 1];
	}

	for (int i = 0; i < T; i++) {
		cout << Dp[arr[i]]<<'\n';
	}
}

int main(void) {
	Input();
	Solve();
	
}