[백준 9461번/C언어] 파도반 수열, 동적계획법으로 풀이

백준 9461번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 

백준 9461번: https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

문제 내용은 아래와 같습니다. 

 

이 문제 역시 이전에 업로드한 다른 DP를 이용한 문제와 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 블로그를 참고해 주시기 바랍니다. 저 역시 동적계획법 문제를 처음 접해보기 때문에 다양한 글들을 꼼꼼히 읽어본 후, 가장 기초적인 문제부터 풀고 있습니다. 

https://didu-story.tistory.com/220

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

동적계획법을 이용하기 위해서는 우선 점화식(Recurrence Relation)을 먼저 파악할 수 있어야 합니다. 점화식을 파악하기 위해 우선 n이 점점 늘어남에 따라 달라지는 결과값을 쭉 나열하여 적어보았습니다. 

P(1) = 1
P(2) = 1
P(3) = 1
P(4) = 1 + 1 = 2
P(5) = 2
P(6) = 1 + 2 = 3
P(7) = 1 + 3 = 4
P(8) = 1 + 4 = 5
P(9) = 2 + 5 = 7
P(10) = 2 + 7 = 9
P(11) = 3 + 9 = 12
P(12) = 4 + 12 = 16
P(13) = 5 + 16 = 21
P(14) = 7 + 21 = 28

여기까지 적고 나서야 저는 점화식을 찾아낼 수 있었습니다. 그렇게 발견한 점화식은 다음과 같습니다.

P(n) = P(n-5) + P(n-1) (n > 5 일때)

 

이렇게 찾은 점화식을 바탕으로 코드를 아래와 같이 짜보았습니다. 결과부터 말씀드리자면 아래 코드는 '시간초과'로 정답처리되지 못했습니다. 그럼에도 아래 방식 역시 DP의 한 가지 방법이기 때문에 코드에 대해 간략히 설명하고 넘어가겠습니다. 아래 코드는 동적계획법 중 Top Down 방식에 해당합니다. n=1인 경우부터 차근히 계산해 올라가는 Bottom Up 방식과는 달리 Top Down 방식은 n이 구하고자 하는 값일 때부터 내려가면서 구하며, 따라서 주로 재귀함수를 사용하게 됩니다.

아래 코드를 보시면, 우선 res배열을 전역변수로 선언하여, 점화식이 적용되기 이전의 값들(n <= 5일 때)을 입력해 줍니다. 그 이후 P(n)부터 시작해서 재귀함수를 통해 내려가면서 값을 구해 채워 넣는 양상을 볼 수 있습니다. 

#include <stdio.h>

int res[101] = {0, 1, 1, 1, 2, 2};

int P(int n) {
    if (n <= 0) return 0;
    if (res[n] > 0) return res[n];
    else return P(n-5) + P(n-1);
}

int main() {
    int t, n;
    scanf("%d", &t);
    
    while (t > 0) {
        t--;
        scanf("%d", &n);
        printf("%d\n", P(n));
    }
}

 

하지만 이 코드는 시간초과로 인해 오답처리가 되었습니다. 그래서 주로 시간복잡도가 더 낮다고 여겨지는 Bottom Up 방식으로 다시 구현해 보았습니다. 앞서 언급된 것처럼 Bottom Up 방식은 n이 최솟값일 때부터 올라가면서 값을 구해 최종적으로 원하는 값을 얻어내는 방식입니다. 따라서 재귀함수 대신 반복문을 사용하게 됩니다.

이렇게 Bottom Up 방식을 사용하고도 처음에는 오답처리가 되었는데요, 결괏값이 int 범위를 벗어날 수 있음에도 이를 잘 설정해주지 않아서 발생한 오답이었습니다. 따라서 아래 res 배열의 경우 type을 long unsigned로 처리해 주었습니다. 또, Top Down 방식에서 전역변수였던 res 배열을 지역변수로 설정해 주었습니다. 함수가 main 함수 하나이므로 굳이 전역변수로 설정해 줄 필요가 없기 때문입니다. 

아래 코드를 보면 이전에 재귀함수로 처리했던 것을 for문을 통해 처리하고 있음을 볼 수 있습니다. 점화식은 완벽히 동일하나 구현 방식만 바꾸어 시간을 줄인 것이라고 생각하시면 됩니다. 주로 함수를 호출할 때, 시간이 많이 소요되어 반복문으로 처리할 수 있는 것은 재귀함수가 아닌 반복문으로 처리해 주는 것이 시간 복잡도 면에서 효율적입니다. 

#include <stdio.h>

int main() {
    int t, n;
    scanf("%d", &t);
    
    long unsigned int res[101] = {0, 1, 1, 1, 2, 2};
    while (t > 0) {
        t--;
        scanf("%d", &n);
        
        for (int i = 6; i <= n; i++) {
            if (res[i] > 0) continue;
            else res[i] = res[i-5] + res[i-1];
        }
        printf("%lu\n", res[n]);
    }
}

 

위와 같이 코드를 입력하면 정답처리 되는 것을 볼 수 있습니다.