[DynamicPrograming]BAEKJOON9095 - 1, 2, 3 더하기

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

 

 

이 문제는 백준 DP중 가장 많이 푼 문제이며 한편으론 DP로 풀지 않아도 되는 이상한 문제이다.

일단 이 문제는 초보자가 풀기에는 딱 좋은 문제인데 어떻게 푸는지 보도록 하자.

 

특정 정수 N을 만들기 위해서 0에서 붙어 1혹은 2혹은 3을 더하는 문제이다.

즉 1혹은 2혹은 3을 더하여 N을 만들 수 있는 경우의 수를 모두 찾는 것이다.

 

이 문제는 모든 경우의 수를 계산하는 완전탐색(브루트포스)를 이용하여 풀 수 있다.

다만 원래라면 시간 제한에 걸리게되는데 여기서는 N의 상한선이 11밖에 되지 않는다.

 

4를 구하는 방법

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

총 7가지

 

모든 경우의 수를 나열하는 문제는 트리를 그려가면서 보면 위처럼 나온다.

위는 4를 구하는 방법인데 총 7가지가 나오는걸 알 수 있다.

시간 복잡도는 일반적으로 계산하면 O(3^N)이 나오게된다.

하지만 실제로 계산해보면 3^N보다는 월등히 적게 계산하는데 그 이유는 안하는 경우의 수가 매우 많기 때문이다.

다 계산해야 실제 시간복잡도를 알 수 있지만 여기서는 패스하겠다.

어쨋든 일반적인 완전탐색을 사용할경우 어마어마한 시간을 사용하는걸 알 수 있다.

 

완전탐색을 하는 방법은 재귀함수를 이용하는 방식(메모이제이션)과 for문을 이용한 방식(타뷸레이션)이 있다.

여기서는 메모이제이션을 이용한 방식으로 푸는 법을 알아보자.

 

void f(int n) {
    if (n == N) {
        cnt++;
    }

    if (n + 3 <= N) {
        f(n + 3);
    }
    if (n + 2 <= N) {
        f(n + 2);
    }
    if (n + 1 <= N) {
        f(n + 1);
    }
}

 

재귀함수를 짜본적이 없다면 지금부터라도 익숙해 져야한다.

재귀를 짜려면 종료되야하는 지점인 배이스 케이스를 먼저 작성해야한다.

이 모든 경우의 수를 구하는 재귀 함수 f는 0부터 시작해서 특정한 수 N을 완성해 나갈것이다.

그리고 그 N이 되면 더이상 함수를 실행하지 않고 종료를 할것이다.

그리고 마지막 경우에 도달했다면 cnt를 늘려준다.

 

#include <iostream>
#include <vector>

using namespace std;

int T;
int N;
vector<int> ARR;
vector<int> results;
int cnt;
int tmp;

void f(int n) {
    if (n == N) {
        cnt++;
    }

    if (n + 3 <= N) {
        f(n + 3);
    }
    if (n + 2 <= N) {
        f(n + 2);
    }
    if (n + 1 <= N) {
        f(n + 1);
    }
}

int main() {
    //init
    {
        cin >> T;
        ARR.push_back(0);
        results.push_back(0);
        for (int t = 1; t <= T; t++) {
            cin >> tmp;
            ARR.push_back(tmp);
        }
    }

    //logic
    {
        for(int t=1;t<=T;t++){
            cnt = 0;
            N = ARR[t];
            f(0);
            results.push_back(cnt);
        }
    }

    //output
    {
        for(int t=1;t<=T;t++){
            cout << results[t] << endl;
        }
    }
    return 0;
}

이 코드를 사용해서 문제를 풀면 두가지의 문제점이 있다.

먼저 시간복잡도가 O(3^N)으로 매우 높다는점, 그리고 큰 수를 사용할 수 없다는 점이다.

하지만 이 문제로 백준에 넣어도 통과는 되는데 그 이유는 11까지 밖에 연산하지 않기 때문이다.

11까지 연산량은 필자가 직접해본결과 1104번 밖에 돌지 않는데 이는 1초도 걸리지 않기 때문에 충분한 시간이다.

그래서 사실 이 문제는 DP를 도입하지않고 완전탐색만으로 풀 수 있는 쉬운 문제이다.

괜히 정답률이 60%대가 아니라는 이야기이다.

 

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

int T;
int N;
ll cnt;
vector<ll> memo;

ll f(int n) {
    if (n == N) {
        return 1;
    } else {
        ll result = 0;
        if (n + 3 <= N) {
            if (memo[n + 3] == 0) {
                memo[n + 3] = f(n + 3);
            }
            result += memo[n + 3];
        }
        if (n + 2 <= N) {
            if (memo[n + 2] == 0) {
                memo[n + 2] = f(n + 2);
            }
            result += memo[n + 2];
        }
        if (n + 1 <= N) {
            if (memo[n + 1] == 0) {
                memo[n + 1] = f(n + 1);
            }
            result += memo[n + 1];
        }
        return result;
    }
}

int main() {
    //init
    {
        cin >> T;
    }

    //repeat
    for (int t = 1; t <= T; t++) {
        //init
        {
            cin >> N;
            cnt = 0;
            memo.clear();
            memo.resize(N + 1, 0);
        }

        //logic
        {
            cnt = f(0);
        }

        //output
        {
            cout << cnt << endl;
        }
    }
    return 0;
}

그럼 메모이제이션을 도입하고 숫자를 큰 숫자도 가능하게 하려면 위처럼 코드를 짜면된다.

실제 여러분의 코드는 30이상부터 엄청나게 오랜시간동안 연산을 하게 될것이다.

또한 40이상의 수는 오버플로우로 제대로 표현 못할것이다.

문제 조건상 11이하의 수가 들어가므로 위의 처리를 안해줘도 무방하지만,

여러분이 DP를 배우는 입장에서 메모이제이션은 익히는게 좋다.

 

if (n + 3 <= N) {
    result += f(n + 3);
}

메모이제이션이 뭔지 알려면위의 코드를 보자.

우리는 f(n+3)의 결과값을 구하고싶다.

하지만 이는 중복계산될 수 있다.

f(n+3)이 여러번 호출될 가능성이 있다.

문제는 f(n+3)은 또다시 f(n+3+1),f(n+3+2),f(n+3+3)을 호출할 가능성이 생긴다.

물론 아래의 녀석들도 자식들을 3개씩 더 호출할 수 있다.

이렇게 중복 호출을 막으려면 이 때의 값을 저장해 놓는 것이다.

이를 메모이제이션이라고한다.

 

if (n + 3 <= N) {
    if (memo[n + 3] == 0) {
        memo[n + 3] = f(n + 3);
    }
    result += memo[n + 3];
}

이렇게 memo[n+3]이 있는지 확인하고(0이 아닌지확인하고) 0이라면 함수를 계산해서 값을 넣는다.

만약에 0이 아니라면 이미 구했던 것이므로 메모의 값을 넣는다.

 

#include <iostream>
#include <vector>

using namespace std;

int T;
int N;
vector<int> ARR;
vector<int> memo;
vector<int> results;
int tmp;
int result;

int main() {
    //init
    {
        cin >> T;
        ARR.push_back(0);
        results.push_back(0);
    }

    //repeat
    for (int t = 1; t <= T; t++) {
        //init
        {
            cin >> tmp;
            ARR.push_back(tmp);
            N = ARR[t];
            memo.clear();
            memo.resize(N + 1, 0);
            memo[0] = 1;
        }

        //logic
        {
            for (int n = 1; n <= N; n++) {
                result = 0;
                if (n - 1 >= 0) {
                    result += memo[n - 1];
                }
                if (n - 2 >= 0) {
                    result += memo[n - 2];
                }
                if (n - 3 >= 0) {
                    result += memo[n - 3];
                }
                memo[n] = result;
            }
            results.push_back(memo[N]);
        }

        //output
        {
            cout << results[t] << endl;
        }
    }

    return 0;
}

만약 나는 재귀함수가 아닌 for문을  쓰고싶다면 for문을 써도 무방하다.

같은 로직을 for문으로 짠 것이다.

여기서도 memo에 넣는데 for문과 재귀의 차이점은

재귀는 필요한 것만 계산하고(모두를 계산하지는 않음)

for문은 필요하건 안하건 모두를 계산하게된다.

모두를 구하지 않는다면 재귀가 시간이 더 빠르게 된다.

다만 보통 알고리즘 테스트에서는 모두를 다 구하게 하므로 for문을 쓰는 방법 역시 유효하다.

이렇게 미리 모든 값을 다 구하는 것은 메모이제이션이라고 하지 않고 타뷸레이션이라고 한다.

 

메모이제이션이나 타뷸레이션이나 둘다 메모이제이션이라고 부르는 경향이 있어서 적당히 알아들으면된다.