[9461] 파도반 수열, c++

한줄 후기 : long long ..

 

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

9461번: 파도반 수열

 

 

다이나믹 프로그래밍 문제

처음에 dp 배열을 int형으로 선언했다 틀렸다. 100을 넣어보니 dummy value 나옴

long long 형으로 선언해야한다.

 

#include <iostream>
using namespace std;
int main(){
	int t;
	long long dp[101];
	cin >> t;
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 1;
	dp[3] = 1;
	while(t--){
		int n;
		cin >> n;
		for(int i=4; i<=n; i++){
			dp[i] = dp[i-2] + dp[i-3];
		}
		cout << dp[n] << endl;
	}
	return 0;
}