9095번

9095 - 1 , 2 , 3 더하기

문제의 조건이 굉장히 작아서 완전탐색으로 풀 수 있다고 생각했다.

하지만 값이 커질 경우에는 메모이제이션을 이용해야 할 것 같다.

그래서 완전탐색, DP, 그리고 추가로 내가 PS를 처음시작했을 때 코드ㅋㅋㅋㅋ 이렇게도 풀었구나 싶은 코드

1. 완전탐색

재귀 함수를 통해서 더해주면서 n값과 일치할 때까지 실행되도록 코드를 작성하였다.

<완전탐색 정답 코드>

#include<iostream>
 
using namespace std;
int ans;
int n;
void go(int num)
{
    if (num > n)
    {
        return;
    }
 
    if (num == n)
    {
        ans += 1;
        return;
    }
 
    go(num + 1);
    go(num + 2);
    go(num + 3);
 
    return;
 
}
int main()
{
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        ans = 0;
        cin >> n;
 
        go(0);
 
        cout << ans << endl;
    }
 
    return 0;
}

2. DP

D[N]=N을 만드는 방법의 갯수

기저 사례에 대해서 하나 하나 조건문을 만들어 주었다.

<DP 정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
int ans;
int n;
int D[11];
int go(int num)
{
    if (num == 0)
    {
        return 1;
    }
    if (num==1)
    {
        return 1;
    }
    if (num == 2)
    {
        return 2;
    }
 
    if (D[num] != -1)
    {
        return D[num];
    }
 
 
    D[num] = go(num - 1) + go(num - 2) + go(num - 3);
 
 
    return D[num];
 
}
int main()
{
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        memset(D, -1, sizeof(D));
        ans = 0;
        cin >> n;
 
        cout << go(n) << endl;
    }
 
    return 0;
}

3. 10중 for문 (초창기 나의 모습)

이렇게 정직하게 아무것도 모를 때 풀 수 있었구나 하는 경외감이 든다...

<10중 for문 정답 코드>

using namespace std;
 
int T;
int num;
int temp;
int size;
deque<int> c;
 
int main()
{
    cin >> T;
    while (T--)
    {
        int cnt=0;
        cin >> num;
        for (int a = 1; a <= 3; a++)
        {
            if (a == num){ cnt++; }
            for (int b = 1; b <= 3; b++)
            {
                if (a + b == num){ cnt++; }
                for (int c = 1; c <= 3; c++)
                {
                    if (a + b + c == num){ cnt++; }
                    for (int d = 1; d <= 3; d++)
                    {
                        if (a + b + c + d == num){ cnt++; }
                        for (int e = 1; e <= 3; e++)
                        {
                            if (a + b + c + d + e == num){ cnt++; }
                            for (int f = 1; f <= 3; f++)
                            {
                                if (a + b + c + d + e + f == num){ cnt++; }
                                for (int g = 1; g <= 3; g++)
                                {
                                    if (a + b + c + d + e + f + g == num){ cnt++; }
                                    for (int h = 1; h <= 3; h++)
                                    {
                                        if (a + b + c + d + e + f + g + h == num){ cnt++; }
                                        for (int i = 1; i <= 3; i++)
                                        {
                                            if (a + b + c + d + e + f + g + h + i == num){ cnt++; }
                                            for (int j = 1; j <= 3; j++)
                                            {
                                                if (a + b + c + d + e + f + g + h + i + j == num){ cnt++; }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        
        c.push_back(cnt);
    }
 
    size = c.size();
    
    for (int i = 0; i < size; i++)
    {
        cout << c.front()<< endl;
        c.pop_front();
    }
 
    return 0;
}