[백준 15988, c++] 1,2,3 더하기 3(dp: topDown, bottomUp)

문제 번호

• 15988(https://www.acmicpc.net/problem/15988)

문제 및 입/출력

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

 

예제 입력1

3 4 7 10

예제 출력1

7 44 274

 

문제 풀이

BOJ 9095(1,2,3 더하기) 문제에서 조금 변형된 문제이다. 알고리즘 측면에서는 9095번 소스에서 변화를 줄 필요가 없었고, 다만 n의 범위가 기존 10에서 1000000으로 100000배가 늘어난것이 포인트이기에 데이터를 담는 변수의 데이터 타입을 변화시켜 주었다. (int -> long long)

---

Dynamic Programming(DP)를 통해 간단히 풀 수 있는 문제이다.

 

점화식을 구하기 위해 n을 5까지 나올 수 있는 경우의 수를 구했다.

 

n = 1, cnt = 1;

n = 2, cnt = 2;

n = 3, cnt = 4;

n = 4, cnt = 7;

n = 5, cnt = 13

....

그 결과 규칙이 보였고, 규칙으로 아래와 같은 점화식을 만들 수 있었다.

-> 점화식 : D[n] = D[n-1] + D[n-2] + D[n-3]

 

---

그리고 이번 문제를 풀면서 9095번 문제를 풀면서 내가 실수한점, 그리고 새로운 것들을 배울 수 있었다. 

 

실수한것은 메모이제이션(memoization)의 중요성을 모르고 제대로 구현을 안해놓은 것이다. 

9095번 재귀부분에 memoization을 사용안한 실수

topDown 재귀부분에 계산되는 중간의 과정을 저장하지않고, 최종값만 return 받아서 main문 변수에 저장하는 형태이다. 이렇게되면 9095같은 범위가 작은 간단한 문제에서는 잘 넘어갔을지 모르지만 이번 문제같은 큰 범위가 주어졌을때는 치명적인 문제를 가져오고만다... 

그렇기 때문에 top-Down으로 가는동안 계산되는 값들을 memoization 해주어야 한다.

 

그리고 9095 문제와 이번 15988문제는 test_case가 주어진다는 사실을 가볍게 넘기면 안된다. test_case인 t를 설정하고 t만큼 n을 입력받는데, n을 입력받을때마다 topDown 이나 bottomUp 함수에 가서 1~n까지의 연산을 반복한다면??.... 정말 바보같은 짓이다.

 

그짓을 이전문제에서 했다..^^

 

이번문제에서는 그 문제점을 파악했고, test_case를 입력받기전에 미리 MAX 값 까지의 결과값을 계산해서 memoization 해놓고, test_case와 각각의 n을 입력받아 memoization된 값에서 바로바로 불러와서 출력하는 형태로 소스를 수정했다.

 

memoization을 고려하여 수정

 

이렇게해서 bottomUp으로 코드를 visual studio에서 돌리면 문제가 없이 동작하지만, topDown으로 돌리면 코드는 정상적으로 돌아가지 않는다. 하지만 백준에서는 정답을 외친다..ㅎㅎ

 

이 부분은 재귀함수의 스택오버플로우 문제이다. 함수가 호출될 때 스택 메모리를 사용하게 되는데 재귀호출은 함수가 꼬리에 꼬리를 물고 실행되기 때문에 계속해서 스택 메모리에 쌓이게 된다. 이렇게 계속 호출되다 메모리가 부족해 에러가 나는것이다.  

 

그럼 왜 백준에서는 통과인데, visual studio에서는 에러가 나는것일까?

 

그것은 백준과 visual studio에서 요구하는 스택오버플로우 크기가 다르기 때문이다.

 

소스 코드

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
#define MAX 1000000
 
long long Dp[MAX + 1];
 
int init[3] = { 1,2,4 };
 
long long topDown(int n) {
    if (Dp[n] > 0) {
        return Dp[n];
    }
    else {
        if (n <= 3) {
            Dp[n] = init[n - 1];
        }
        else {
            Dp[n] = topDown(n - 1) + topDown(n - 2) + topDown(n - 3);
            Dp[n] %= 1000000009;
        }
        return Dp[n];
    }
}
 
void bottomUp(int n) {
    Dp[1] = 1;
    Dp[2] = 2;
    Dp[3] = 4;
 
    for (int i = 4; i <= n; i++) {
        Dp[i] = Dp[i - 1] + Dp[i - 2] + Dp[i - 3];
        Dp[i] %= 1000000009;
    }
}
 
int main() {
    int t, n;
    bottomUp(MAX);
    //topDown(MAX);
 
    scanf("%d", &t); // test case
    while (t--) {
        scanf("%d", &n);
        printf("%lld\n", Dp[n]);
    }
    return 0;
}
 
 
/*
n = 1, cnt = 1;
n = 2, cnt = 2;
n = 3, cnt = 4;
n = 4, cnt = 7;
n = 5, cnt = 13
....
점화식 : D[n] = D[n-1] + D[n-2] + D[n-3]
*/