[9461] 파도반 수열

---

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

9461번: 파도반 수열

지독하게 실버만 패는 사람,,

 

 

이 문제는 DP + 수학이 섞여 있는 문제이다. 

나선형으로 돌아가는 형식이라 규칙이 있을 것이라 생각하고 직접 그려보며 문제를 풀었다.

P(9)부터 규칙이 존재함을 발견했다. 

A[i] = A[i - 1] + A[i - 5];

바로 그 전 값(i-1)과, 5번째 전에 있던 값(i-5)의 합이 현재 i의 값임을 알아냈다.

 

 

근데 그냥 했더니 틀렸다.

알고보니 int형이라 overflow가 난 것이었다.

 

그래서 int -> unsigned long long int로 바꿔주었더니 해결됐다.

아래는 전체 코드이다.

#include <iostream>
using namespace std;

unsigned long long int A[101] = { 0,1,1,1,2,2,3,4,5, }; // 초기 값 설정

void dp() {
	for (int i = 9; i <= 100; i++) {
		A[i] = A[i - 1] + A[i - 5];
	}
}

int T, N;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	dp();

	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N;
		cout << A[N] << endl;
	}
}