[백준 / BOJ / SILVER 3] 9095 번 : 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

문제 접근 방법

• 여러가지 방식으로 풀 수 있는 문제입니다.
• n중 for문을 사용하여 구할수도 있고, 재귀를 이용해서도 구할 수 있으며, DP로도 문제를 풀 수 있습니다.
• n중 for문의 경우 값이 일치하는지를 모든 경우에 체크하는 방식으로 진행한다
• 재귀의 경우 맞는 값을 찾았을 경우 정답 출력값의 변수를 증가 시키고 값이 입력 값을 초과했을 경우 return을 해주고, 이 두 경우가 아닐 경우에 각 1, 2, 3 을 더한 함수를 호출하는 방식으로 진행한다.
• DP의 경우에는 점화식을 만들어야 하는데, n을 만들기 위해서 1, 2, 3을 사용하기 때문에 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]가 성립함을 알 수 있다.

아래는 코드입니다.

n중 for문을 사용한 코드입니다.

#include <iostream>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int testNum, num;
    int ary[] = { 1,2,3 };
 
    cin >> testNum;
 
    while (testNum--)
    {
        int count = 0;
        cin >> num;
 
        for (int a = 0; a < 3; a++) 
        {
            if (ary[a] == num)
            {
                count++;
            }
            for (int b = 0; b < 3; b++) 
            {
                if (ary[a] + ary[b] == num)
                {
                    count++;
                }
                for (int c = 0; c < 3; c++) 
                {
                    if (ary[a] + ary[b] + ary[c] == num)
                    {
                        count++;
                    }
                    for (int d = 0; d < 3; d++) 
                    {
                        if (ary[a] + ary[b] + ary[c] + ary[d] == num)
                        {
                            count++;
                        }
                        for (int e = 0; e < 3; e++) 
                        {
                            if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] == num)
                            {
                                count++;
                            }
                            for (int f = 0; f < 3; f++) 
                            {
                                if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] == num)
                                {
                                    count++;
                                }
                                for (int g = 0; g < 3; g++) 
                                {
                                    if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] == num)
                                    {
                                        count++;
                                    }
                                    for (int h = 0; h < 3; h++) 
                                    {
                                        if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] + ary[h] == num)
                                        {
                                            count++;
                                        }
                                        for (int i = 0; i < 3; i++) 
                                        {
                                            if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] + ary[h] + ary[i] == num)
                                            {
                                                count++;
                                            }
                                            for (int j = 0; j < 3; j++) 
                                            {
                                                if (ary[a] + ary[b] + ary[c] + ary[d] + ary[e] + ary[f] + ary[g] + ary[h] + ary[i] + ary[j] == num)
                                                {
                                                    count++;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        cout << count << "\n";
    }
 
    return 0;
}

 

재귀를 사용한 코드입니다.

#include <iostream>
using namespace std;
 
int answer = 0;
 
void sum(int count, int ans)
{
    if (count == ans) {
        answer++;
        return;
    }
    else if(count > ans)
    {
        return;
    }
 
    for (int i = 1; i <= 3; i++)
    {
        sum(count + i, ans);
    }
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int num;
    cin >> num;
 
    while(num--)
    {
        int a;
        cin >> a;
 
        sum(0, a);
        cout << answer << "\n";
        answer = 0;
    }
 
    return 0;
}

 

DP를 사용한 코드입니다.

0일 때 아무것도 더하지 않아도 1개가 나오므로 최초값은 1에서 부터 시작하게 하였습니다.

#include <iostream>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int a, b;
    cin >> a;
 
    while (a--)
    {
        int check[12] = { 1, };
 
        cin >> b;
 
        for (int i = 1; i <= b; i++)
        {
            if (i - 1 >= 0)
            {
                check[i] += check[i - 1];
            }
            if (i - 2 >= 0)
            {
                check[i] += check[i - 2];
            }
            if (i - 3 >= 0)
            {
                check[i] += check[i - 3];
            }
        }
        cout << check[b] << "\n";
    }
 
    return 0;
}