[ 백준 9095 ] 1,2,3더하기 (C++)

백준 1,2,3더하기(9095) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 테스트 케이스의 갯수가 입력으로 주어지고, 각 테스트 케이스마다 정수 하나가 입력으로 주어진다.

- 그 정수를 1,2,3 3개의 숫자만을 이용해서 더해서 그 수를 출력시켜야 하는 경우의 수를 출력시키는 문제이다.

[ 문제풀이 ]

1) 작은 숫자부터 생각을 해보면

   1이 주어졌을 때 1을 1,2,3 3개를 이용해 만들 수 있는 경우의 수는 (1) 1개이다.

   2 는 (1+1, 2) 2개이다. 3은 (1+1+1 , 1+2, 2+1, 3) 4개이다.

   4의 경우는 ?? 4는 크게보면 (1+3, 2+2, 3+1) 3가지가 있는데, 이 중에서

   (4-3)+3 에서 3을 만드는 경우의 수 = 4개

   (4-2)+2 에서 2를 만드는 경우의 수 = 2개

   (4-1)+1 에서 1을 만드는 경우의 수 = 1개

   총 7개가 된다. 실제로 문제에서 주어진 대로 7가지의 경우의 수가 존재한다.

   위에서, 1,2,3을 (4-3 , 4-2, 4-1)로 표시한 것은 이러한 과정을 통해서 점화식을 도출해 낼 수 있기 때문이다.

2) 위의 이론을 통해서 점화식을 도출해 내보면 

   Arr[N] = Arr[N-1] + Arr[N-2] + Arr[N-3]이 성립하게된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 11
using namespace std;
 
int N;
int Arr[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    // 1을 만들수 있는 방법 = 1 (1)
    // 2를 만들수 있는 방법 = 2 (1+1) , (2)
    // 3을 만들수 있는 방법 = 3 (1+1+1) , (1+2) , (2+1) , (3)
    // 4를 만들수 있는 방법 = ??
    Arr[0] = 0;
    Arr[1] = 1;
    Arr[2] = 2;
    Arr[3] = 4;
 
    for (int i = 4; i <= N; i++)
    {
        Arr[i] = Arr[i - 1] + Arr[i - 2] + Arr[i - 3];
    }
 
    cout << Arr[N] << endl;
 
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
 
    for (int T = 1; T <= Tc; T++)
    {
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}