[알고리즘 문제] 백준9095 - 1,2,3 더하기

예전에 비슷한 문제가 코테에 나왔었는데, 그떄 못풀었기 때문에 이번에 완벽하게 이해하고 넘어가고 싶어 한번 풀어 보았습니다.

알고리즘 분루뉸 DP로 나와있는데, 저는 DP를 정확히 잘 모르기 때문에 먼저 재귀적인 방법으로 문제를 풀었습니다.

 

1. 재귀적 방법

#include <iostream>

using namespace std;

int result = 0;

void recur(int n, int sum)
{

    if (sum > n)
    {
        return;
    }
    if (sum == n)
    {
        result++;
        return;
    }

    for (int i = 1; i <= 3; i++)
    {
        sum += i;
        recur(n, sum);
        sum -= i;
    }
}
int main()
{

    int test_case = 0;
    int n;

    cin >> test_case;
    for (int i = 0; i < test_case; i++)
    {
        cin >> n;
        recur(n, 0);
        cout << result << "\n";
        result = 0;
    }

    return 0;
}

일단 재귀적인 방법은 직관적입니다.

재귀함수 안에서 for문을 계속 돌립니다(범위는 1~3인데 1,2,3순으로 계속 더해줍니다)

 

기저조건은 sum > n이거나 sum==n인 경우 입니다. 

처음에 sum==n인 경우만 넣었는데, 이런 경우는 숫자가 1씩 증가 하는게 아니라 2,3을 더하게 되면 n과 같지 않고 그 수를 갑자기 넘어버리기 때문에 sum > n조건도 추가해야 합니다.

 

이렇게 재귀함수를 돌다가 sum==n인 경우는 1,2,3으로 조합할 수 있는 하나의 경우를 찾았기 때문에 result++를 해줍니다.

 

2.DP

#include <iostream>

using namespace std;

int cache[11];

int search(int n)
{
    for (int i = 4; i <= n; i++)
    {
        cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3];
    }
    return cache[n];
}

int main()
{
    cache[1] = 1;
    cache[2] = 2;
    cache[3] = 4;

    int test_case;
    cin >> test_case;

    for (int i = 0; i < test_case; i++)
    {
        int n;
        cin >> n;
        cout << search(n) << "\n";
    }
    return 0;
}

 

재귀로 문제를 풀긴 했지만, 알고리즘 분류가 DP로 되어있기 때문에 다시 DP로 문제를 풀어 보았습니다.

 

먼저 각 숫자에 대해 1,2,3으로 만들 수 있는 조합을 살펴봅시다

1 : (1) ->1 가지

2 : (1,1) , (2) ->2 가지

3 : (1,1,1) , (1,2) , (2,1,) , (3) -> 4가지

....

4 : (1,3) -> 3을 만들 수 있는 경우의 수

     (2,2) -> 2를 만들 수 있는 경우의 수

     (3,1) -> 1을 만들 수 있는 경우의 수

 

5 : (1,4) -> 4를 만들 수 있는 가지의 수

     (2,3) -> 3을 만들 수 있는 가지의 수

     (3,2) -> 2를 만들 수 있는 가지의 수

 

6: ....

 

이렇게 앞에서 구한 값을 이용하여 현재의 값을 구할 수 있다.

정수n에 대해 이를 나타낼 수 있는 경우의 수는(위에서 구한 방법) cache[n]에 저장한다. 

위에서 1,2,3으로 4를 나타낼 수 있는 방법은 (3,2,1)를 만들 수 있는 경우의 수를 더한 것이기 때문에

cache[n] = cache[n-1] + cache[n-2] + cache[n-3]이 된다