[백준(BOJ)] 9461번: 파도반 수열 (Dynamic Programming, C++)

📝 문제풀이 과정

---

P(n) = 1 (0 <= n < 3)
P(n) = P(n-2) + P(n-3) (n >= 3)

0 이상 2 이하의 수에 대해서는 1의 값을 갖고, 3 이상부터는 점화식 F(n) = F(n-2) + F(n-3) 이 된다.

 

n = 3 P(3) = P(1) + P(0) = 1 + 1 = 2
n = 4 P(4) = P(2) + P(1) = 1 + 1 = 2
n = 5 P(5) = P(3) + P(2) = 2 + 1 = 3
n = 6 P(6) = P(4) + P(3) = 2 + 2 = 4
n = 7 P(7) = P(5) + P(4) = 3 + 2 = 5
n = 8 P(8) = P(6) + P(5) = 4 + 3 = 7
n = 9 P(9) = P(7) + P(6) = 5 + 4 = 9
n = 10 P(10) = P(8) + P(7) = 7 + 5 = 12
...

 

주의할 점이, N이 100같이 커지면 integer 범위를 벗어나기 때문에 python 같이 integer 범위가 크지 않은 C, C++ 등은 범위를 신경써줘야 한다. long 형으로 수열 P의 형을 바꿔주고, 출력 시 %d가 아닌 %ld를 사용하면 해결할 수 있다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <deque>
using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    for(int i=0; i<T; i++){
        int N;
        scanf("%d", &N);
        deque<long long> P(N, 0);

        for(int i=0; i<3; i++){
            P[i] = 1;
        }
        for(int i=3; i<N; i++){
            P[i] = P[i-2] + P[i-3];
        }
        printf("%ld\n", P[N-1]);
    }
}

 

 

👏 결과

---