9461 파도반 수열

파도반 수열 9461

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
// 9461 파도반 수열

const int MAX = 100;

int main(){
	int n, T;
	cin >> T;
	cin.ignore();
	unsigned long long seq[MAX + 1] = {1,1,1,2,2,3,4,5};

	while(T--){
		cin >> n;
		cin.ignore();
		for(int i = 8; i < n; i++){
			seq[i] = seq[i - 2] + seq[i - 3];
		}
		
		cout << seq[n - 1] << endl;
		
	}
	
}

 

해설

---

풀이

나열해서 간단한 점화식을 찾는 문제였다. $$a_n = a_{n-2} + a_{n-3} $$

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

N 의 한계가 100 이므로 int 의 값을 훌쩍 뛰어넘을 수 있을거란 점을 간과하였다. 계산하는 배열의 값을 unsigned long long 으로 재선언하여 해결하엿다.