[백준 15989번] 1, 2, 3, 더하기 4

문제 링크

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

 

문제 요약

정수 N이 주어졌을 때, 1, 2, 3의 합으로 N을 나타내는 경우의 수를 찾는 문제이다. 순서만 다른 것은 같은 경우라는 것을 주의해야 한다.

 

문제 풀이

이 문제는 전형적인 동적 계획법(dynamic programming, 이하 DP)로 해결할 수 있다. DP는 상향식과 하향식 두 가지 방법으로 구현할 수 있는데 보통은 하향식 방법이 구현이 쉽고 직관적이다. 하지만 슬라이딩 윈도우, 컨벡스 헐 트릭등 다양한 DP 최적화 전략을 이용하기 위해서라면 상향식 방법도 이용할 줄 알아야 하기 때문에 두 가지 방법으로 모두 구현을 해본다.

 

하향식으로 문제 풀기

상향식으로 문제를 풀 때 가장 먼저 해야 할 일은 재귀적으로 문제를 해결할 수 있는 완전 탐색 코드를 작성하는 것이다. 다음과 같은 함수를 생각해보자.

 

\(\text{calc}(x, last) =\) \(x\)를 \(last\)이상 3 이하의 숫자의 합으로 로 표현할 수 있는 경우의 수

 

순서만 다른 경우는 같은 경우의 수로 계산해야 할 때는 고르는 순서를 한쪽 방향으로 강제하면 쉽게 해결할 수 있기 때문에 함수의 두 번째 인자로 \(last\)를 넣어줬다. 이제 이 재귀 함수는 다시 또 다른 재귀함수들로 표현할 수 있다.

 

\(\text{calc}(x, \text{last}) = \displaystyle\sum_{i=\text{last}}^{3} \text{calc}(x-i, i)\) \(\text{where}\) \(x - i \geq 0\)

 

정의한 재귀함수를 코드로 옮기면 다음과 같다.

int calc(int x, int last) {
    if (x == 0) {
        return 1;
    }
    
    int ret = 0;
    
    for (int i = last ; i <= 3 ; ++i) {
        if (x - i >= 0) {
            ret += calc(x - i , i);
        }
    }
    
    return ret;
}

구현한 재귀함수에 메모이제이션 패턴을 적용하면 상향식 DP로 문제를 풀게 된다. 전체 코드는 아래 더보기를 클릭하면 볼 수 있다.

 

#include <stdio.h>
#include <string.h>

int t, n, cache[10010][4];

int calc(int x, int last) {
    if (x == 0) {
        return 1;
    }
    
    int& ret = cache[x][last];
    
    if (ret != -1) {
        return ret;
    }
    
    ret = 0;
    
    for (int i = last ; i <= 3 ; ++i) {
        if (x - i >= 0) {
            ret += calc(x - i , i);
        }
    }
    
    return ret;
}

int main() {
    scanf("%d", &t);
    
    memset(cache, -1, sizeof(cache));
    
    while (t--) {
        scanf("%d", &n);
        
        printf("%d\n", calc(n, 1));
    }
}

 

상향식으로 문제 풀기

상향식으로 문제를 풀 때는 점화식을 먼저 세워야 한다. 그런데 이 문제 같은 경우 하향식으로 문제를 풀 때 만들었던 재귀함수의 정의를 상향식으로 문제를 풀 때에도 그대로 사용할 수 있다. 

dp[0][1] = 1;

for (int i = 1 ; i < 10010 ; ++i) {
    for (int j = 1 ; j <= 3 ; ++j) {
        for (int k = j ; k <= 3 ; ++k) {
            if (i - k >= 0) {
                dp[i][k] += dp[i - k][j];
            }
        }
    }
}

그런데 이대로 끝내기에는 뭔가 좀 아쉬운 느낌이 든다. 상향식으로 문제를 풀 경우에는 DP 최적화를 할 수 있다고 했는데, 이 문제는 어떻게 DP 최적화를 할 수 있을까? 하향식으로 문제를 풀 때 \(last\) 변수를 이용해 사용하는 숫자의 순서를 강제하고 있었다. 상향식으로 문제를 풀 때 이 순서 강제를 다른 방법으로 할 수 있을까?

 

상향식으로 접근을 하게 되면, 각 숫자 1, 2, 3을 사용 순서를 반복문 내에서 강제할 수 있기 때문에 \(last\) 변수가 없어도 자연스럽게 중복을 제거할 수 있다.

dp[0] = 1;

for (int i = 1 ; i <= 3 ; ++i) {
    for (int j = i ; j < 10010 ; ++j) {
        dp[j] += dp[j - i];
    }
}

이렇게 되면 \(last\) 변수가 없기 때문에 2차원 배열로 관리하던 dp 테이블을 1차원으로 줄일 수 있어 메모리 사용 또한 효율적으로 할 수 있다.  전체 코드는 아래 더보기를 클릭하면 볼 수 있다.

 

#include <stdio.h>
#include <string.h>

int t, n, dp[10010];

int main() {
    scanf("%d", &t);
    
    dp[0] = 1;
    
    for (int i = 1 ; i <= 3 ; ++i) {
        for (int j = i ; j < 10010 ; ++j) {
            dp[j] += dp[j - i];
        }
    }
    
    while (t--) {
        scanf("%d", &n);
        
        printf("%d\n", dp[n]);
    }
}