[백준 / BOJ] - 9461번 파도반 수열 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [9461] 

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

문제

 

 

 

풀이

 

파도반 수열의 규칙성을 찾아보자.

P(1) = 1

P(2) = 1

P(3) = 1 

P(4) = 2 ( P(1) + P(2) )

P(5) = 2 ( P(2) + P(3) )

P(6) = 3 ( P(3) + P(4) )

P(7) = 4 ( P(4) + P(5) )

 

이를 통해 다음과 같은 일종의 피보나치 수열 꼴의 점화식을 생성할 수 있다.

P(N) = P(N-3) + P(N-2)

 

 

코드

 

#include <iostream>
using namespace std;
long long Parray[101] = {0,1,1,};
long long P(int N)
{
    if(N < 3)
        return Parray[N];
    else if(Parray[N] == 0)
        Parray[N] = P(N-2) + P(N-3);
    return Parray[N];
}
int main() {
    int T;
    int N;
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        cin >> N;
        cout << P(N) << '\n';
    }
}

 

 

평가

 

분명히 테스트케이스도 맞고, 점화식도 맞는데 틀리는 경우는 무조건 자료형을 의심해야한다.

피보나치 수열의 값은 N이 커짐에 따라 빠르게 증가하므로, 반드시 long long 자료형을 사용해야한다.