파도반 수열 (feat. 백준, 9461번)

파도반 수열
https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/9461
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int T;
	register long long arr[101] = { 0 };
	arr[1] = arr[2] = arr[3] = 1, arr[4] = arr[2] + arr[1];
	cin >> T;
	for (register int t = 0, N, n; t < T; ++t) {
		cin >> N;
		for (n = 5; n <= N; ++n)
			if (arr[n] == 0)			arr[n] = arr[n - 2] + arr[n - 3];
		cout << arr[N] << endl;
	}
	return 0;
}
// *&)*@*

1. 문제의 지문과 같이 P(1) - P(10) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 입니다.
2. 즉, P(N) = P(N - 2) + P(N - 3) (단, N은 4 이상) 의 수식이 성립됩니다.
3. 단, N의 값이 커질수록 합계 또한 integer 범위를 넘어가기 때문에 long long type으로 변경하였습니다.