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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저, 간단한 예시들을 통해서 문제에 접근해보자.

지금부터 수식을 한 가지 사용할 것인데, F[A] = B 라는 수식을 사용할 것이다.

F[A] = B 의 의미는 "숫자 A를 1, 2, 3의 합으로 만들 수 있는 방법은 총 B가지가 있습니다." 를 의미한다.

#1. '1'만들기

가장 먼저 '1'을 만들 수 있는 방법에 대해서 알아보자.

'1'은 1 하나만 사용함으로써 '1'을 만들 수 있다.

즉, '1'을 만들 수 있는 방법은 총 1가지가 존재한다.

F[1] = 1

#2. '2'만들기

'2'는 2가지 방법이 있다.

1 + 1

2

이렇게 2가지 방법이 있다.

따라서 F[2] = 2 가 된다.

#3. '3'만들기

'3'을 만들 수 있는 모든 방법을 다 적어보자.

1 + 1 + 1

1 + 2

2 + 1

3

이렇게 총 4가지 방법이 있다.

F[3] = 4

#4. '4'만들기

'4'를 만들 수 있는 방법을 모두 적어보자.

1. 1 + 1 + 1 + 1

2. 1 + 2 + 1

3. 2 + 1 + 1

4. 3 + 1

5. 1 + 1 + 2

6. 2 + 2

7. 1 + 3

위와 같이 총 7가지 방법이 있다.

그럼 이 7가지 방법을 토대로 하나의 일반화된 식을 구해보자.

먼저, 위의 7가지 방법 중 1 ~ 4번 방법을 보자.

1. 1 + 1 + 1 + 1

2. 1 + 2 + 1

3. 2 + 1 + 1

4. 3 + 1

위의 4가지 방법에는 한 가지 공통점이 존재한다. 바로, "가장 마지막에 + 1이 붙는다는 것" 이다.

그럼, 가장 마지막에 있는 + 1을 떼어놓고 앞에 식들만 한번 봐보자.

1. 1 + 1 + 1 + 1

2. 1 + 2 + 1

3. 2 + 1 + 1

4. 3 + 1

위의 파랑색으로 칠해진 부분들은 익숙한 식들이다.

바로, #3에서 진행했던 '3'만들기에서 나왔던 식들이기 때문이다.

즉, 숫자 '4'를 만들기 위해서는, '3'을 먼저 만든 후에 뒤에 '1'을 추가적으로 더해주면 된다.

따라서, '4'를 만드는 방법의 수에는 '3'을 만드는 방법의 수가 영향을 미치게 된다.

그 다음 5, 6번 방법을 보자.

5. 1 + 1 + 2

6. 2 + 2

마찬가지로 공통점을 찾아보면, "가장 마지막에 +2가 붙는다는 것" 이다.

그럼, 마지막 + 2를 제외한 앞에 식들만 보게 되면...

5. 1 + 1 + 2

6. 2 + 2

위의 파랑색으로 칠한 식들은, 우리가 #2에서 '2'만들기에서 나왔던 식들이다.

즉, 숫자 '4'를 만들기 위해서는, '2'를 먼저 만든 후에 뒤에 '2'를 추가적으로 더해주면 된다.

따라서, '4'를 만드는 방법의 수에는 '2'를 만드는 방법의 수가 영향을 미치게 된다.

마지막, 7번 방법을 보게 되면, 1 + 3 인데, 이 식에서는 가장 마지막에 + 3이 붙게 된다.

즉, 숫자 '4'를 만들기 위해서는 '1'을 먼저 만든 후에 뒤에 '3'을 추가적으로 더해주면 되는 것이다.

따라서, '4'를 만드는 방법의 수에는 '1'을 만드는 방법의 수가 영향을 미치게 된다.

위의 풀이를 토대로 '4'를 만들 수 있는 경우의 수를 계산해보면..

F[4] = "3을 만드는 방법의 수(뒤에 +1만 붙이면 되기 때문에)" + "2를 만드는 방법의 수(뒤에 +2만 붙이면 되기 때문에)" + "1을 만드는 방법의 수(뒤에 +3만 붙이면 되기 때문에)"

즉, F[4] = F[3] + F[2] + F[1] = 4 + 2 + 1 = 7 이 된다.

위의 식에서 '4'를 'N'으로 바꿔보자.

그럼 F[N] = F[N - 1] + F[N - 2] + F[N - 3]이 된다는 것을 알 수 있다.

이를 점화식으로 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1000010
#define MODULER 1000000009
using namespace std;
 
int N;
long long DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 4;
    for (int i = 4; i <= N; i++)
    {
        DP[i] = (DP[i - 1] + DP[i - 2] + DP[i - 3]) % MODULER;
    }
    cout << DP[N] % MODULER << 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;
}