[백준/C언어] 9461번 - 파도반 수열

백준 웹사이트 "9461번 - 파도반 수열" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

9461번: 파도반 수열

---

소스 코드

#include <stdio.h>

int main(void){
    int T;
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int N;
        scanf("%d", &N);

        long long int P[N+1];
        if(N<4)
            printf("%lld\n", 1);
        else{
            P[1] = 1;
            P[2] = 1;
            P[3] = 1;
            for(int j=4; j<N+1; j++){
                P[j] = P[j-3] + P[j-2];
            }
            printf("%lld\n", P[N]);
        }
    }
}

---

문제 풀이

  대부분의 동적 계획법 문제가 그렇듯, 점화식만 찾으면 코딩은 어렵지 않습니다. 문제 그림을 참고하여, 파도반 수열 \(P(N)\)의 점화식을 찾아봅시다.

  가장 먼저 찾을 수 있는 규칙은 '12 = 3 + 9', '9 = 7 + 2' 와 같이, 바로 전 숫자와 5번 전 숫자를 합하면 다음 숫자가 나온다는 것입니다. 따라서 다음과 같은 수식으로 표현할 수 있습니다.

$$P(N) = P(N-1) + P(N-5)$$

  또한 '12 = 7 + 5', '9 = 5 + 4' 의 규칙도 찾을 수 있으며, 이는 2번 전, 3번 전 숫자를 합해도 다음 숫자가 나온다는 것을 의미합니다. 이는 다음과 같은 수식이 됩니다.

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

  어느 식을 사용해도 상관 없습니다. 하지만 첫 번째 수식의 경우, P[1] ~ P[5] 까지의 값을 모두 선언해줘야 하는 반면, 두 번째 수식은 P[1] ~ P[3] 까지의 값만 선언하면 됩니다. 위의 소스코드 역시 두 번째 수식을 사용합니다.

  코드 작성 중 한 가지 주의할 점은 'long long int' 자료형의 배열을 만드는 것입니다. 최대 100번째 파도반 수 \(P(100)\)까지 계산해야하는데, 이는 int의 범위를 넘기 때문에 고려해줍니다.