백준 9507번 Generations of Tribbles C++

리뷰

이게 실버문제라니! DP로 피보나치 수열을 구하는 것과 동일한 방식

 

문제 풀이

1. 피보나치 수열을 구할 68크기의 벡터를 생성해 준다.
2. 0, 1, 2, 3에 인덱스에 해당하는 값을 미리 할당해 주고, 4부터 68까지는 for문으로 할당해 준다.
3. 각 테스트 케이스 마다 입력 받은 값을 인덱스로 하는 값을 출력해 준다.

 

참고 사항

나중에 값이 매우 커지므로 int형식으로는 오버플로우가 될 것이다.

 

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<long long> fibo(68, 1);
	fibo[1] = 1, fibo[2] = 2, fibo[3] = 4;
	for (int i = 4; i < 68; i++) {
		fibo[i] = fibo[i - 1] + fibo[i - 2] + fibo[i - 3] + fibo[i - 4];
	}
	int t;
	cin >> t;
	while (t--) {
		int c;
		cin >> c;
		cout << fibo[c] << "\n";
	}
}