[BOJ / C++] 15989번 : 1, 2, 3 더하기 4

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

Solved.ac 레벨

실버 I

풀이

#include <bits/stdc++.h>
#define MAX 10001

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    int dp[MAX][4];
    cin >>t;

    for(int i = 1; i <= 3; i++){
        dp[i][1] = 1;
    }
    dp[2][2] = 1;
    dp[3][2] = 1;
    dp[3][3] = 1;

    for(int i = 4; i <= 10000; i++) {
        dp[i][1] = 1;
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
        dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i -3][3];
    }

    while(t--){
        int n;
        cin >> n;

        cout << dp[n][1] + dp[n][2] + dp[n][3] << "\n";

    }


    return 0;
}

오랜만에 풀어본 DP 문제다. 점화식을 도출하는 데에 많은 다른 풀이들을 참고했어야 했다. 시리즈 문제인 '1, 2, 3 더하기'의 이전 문제들을 풀 때는 dp 배열을 1차원으로 선언하는 것만으로도 풀이가 가능했는데, 이 문제는 '중복 제거' 및 '오름차순' 조건이 걸려있기 때문에 2차원 배열을 사용하여야 했다.

 

내가 생각해낸 풀이 방식은 이렇다.

 

1, 2, 3의 합으로 나타낼 수를 i라고 했을 때 j는 각각 1, 2, 3 이하의 수로 나타낼 수 있는 i의 합의 개수라고 했을 때

dp[i][j]라고 dp 배열을 두었다.

 

간단히 예를 들기 위해 문제에서 주어진 예제처럼 4를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 알아보고, 5를 1, 2, 3의 합으로 나타내는 경우까지 확인해보자.

 

먼저 i가 1, 2, 3일 때 dp 배열의 값을 보면 아래와 같다.

i = 1

dp[1][1] = 1
1
dp[1][2] = 0
-
dp[1][3] = 0
-

 

i = 2

dp[2][1] = 1
1 + 1
dp[1][2] = 1
2
dp[1][3] = 0
-

 

i = 3

dp[3][1] = 1
1 + 1 + 1
dp[3][2] = 1
1 + 2
dp[3][3] = 1
3

 

어느정도 규칙이 보이기 시작한다. 이제 i = 4일 경우에서 일반화를 해보자.

 

dp[4][1]

1 + 1 + 1 + 1
-> 1개

1, 2, 3에서 보았듯 i가 몇이 되어도 1로 나타낼 수 있는 합은 1개 뿐이다. (1 = 1, 2 = 1 + 1, 3 = 1 + 1 + 1...)

따라서 4 이전의 수의 dp[i][1] 은 1로 초기화하였다.

 

dp[4][2]

1 + 1 + 2
2 + 2
-> 2개

여기서부터 유심히 살펴보면 두 경우를 아래와 같이 생각해볼 수 있다.

(1 + 1) + 2 

(2) + 2

소괄호로 감싼 부분은 dp[2][1], dp[2][2]에서 구한 값과 같다. 이 경우의 수의 합이 dp[4][2] 인 것으로 추정된다.

 

dp[4][3]

1 + 3
-> 1개

1은 dp[1][1], dp[1][2], dp[1][3]을 모두 더한 값과 같다고 추정된다.

 

이제 i = 5 일때로 확장시켜 보이는 규칙을 확실히 증명해보자.

 

dp[5][1] = 1

1 + 1 + 1 + 1 + 1

dp[5][2] = 2

(1 + 1 + 1) + 2 -> dp[3][1]의 값 + 2
(1 + 2) + 2 -> dp[3][2]의 값 + 2

즉 dp[i - 2][1] + dp[i - 2][2]이라고 생각해도 되겠다.

 

dp[5][3] = 2

(1 + 1) + 3 -> dp[2][1]의 값 + 3
(2) + 3 -> dp[2][2]의 값 + 3

dp[2][3] = 0 이니 이 또한 dp[2][1] + dp[2][2] + dp[2][3]의 값이 dp[5][3] 이라고 생각해도 무리는 없을 것이다. 이는 i = 6 일 때까지 확인해보면 확실히 증명되는 가설이나 여기서는 다루지 않겠다.

즉 dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3]의 값이라고 생각해도 되겠다.

 

따라서 각 경우의 수를 일반화하여 점화식으로 나타내면 아래와 같다.

dp[i][1] = 1 // 모든 수를 1만의 합으로 나타내는 경우는 1가지이다.
dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][2]

n에 대하여 n을 1, 2, 3의 합으로 나타내는 경우의 수는 dp[i][1] + dp[i][2] + dp[i][3]으로 출력해주면 된다.

 

15989번: 1, 2, 3 더하기 4