BOJ-9461
24 Aug 2021범위 고려하기… 오버플로우 조심하기! 이번 기회에 피보나치랑 비슷한 파나도반수열을 알게 되었다.
Panadovan Sequence
P(n) = P(n-2) + P(n-3)
P(0) = P(1) = P(2) = 1
- 구글에서 해당 수열에 대한 점화식을 알게 되었고,
- 백준 질문 답변을 통해 왜 틀렸는지 알 수 있었다. =>
int대신long을 썼더니, 해결! 기하급수적으로 커지는 숫자를 항상 유념하자…⚠
#include<iostream>
using namespace std;
long input[101];
long panadovan(int n) {
long ppp = 1, pp = 1, p = 1, pn = 1;
for (int i=3; i<=n; i++) {
pn = ppp+pp;
ppp = pp;
pp = p;
p = pn;
}
return pn;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
for (int i=0; i<T; i++)
cin >> input[i];
for (int i=0; i<T; i++)
cout << panadovan(input[i]-1) << endl;
return 0;
}
