[백준, C++] 15989 - 1, 2, 3 더하기 4

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

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

 

문제 분석

전형적인 DP 문제같아 보인다. 1만 이하의 정수 N을 1, 2, 3의 합으로 나타내는 방법이 총 몇 가지인지를 구하는 것이고, 전체 경우의 수를 구할 때는 순서를 따지지 않는, 즉 순열이 아닌 조합의 개수를 묻는 문제이다. 문제에서 예시로 제공한 케이스를 살펴보면, N = 4일 때는 아래와 같은 경우의 수가 나온다.

 

4 = 1 + 1 + 1 + 1

4 = 1 + 1 + 2

4 = 1 + 3

4 = 2 + 2

 

DP는 점화식을 구하는 것이 중요하다. 이 문제의 경우 어떻게 점화식을 세울 수 있을까 ?

 

N을 1, 2, 3의 합으로 표현한다면, 이렇게 점화식을 세울 수 있다.

 

N을 1, 2, 3의 합으로 표현하는 경우의 수

= (N - 1)을 1, 2, 3의 합으로 표현한 경우의 수 + (N - 2)를 2, 3의 합으로 표현한 경우의 수 + (N - 3)을 3의 합으로 표현한 경우의 수

 

(여기서 1, 2, 3의 합으로 표현한 경우의 수라는 것은, 1, 2, 3 중 어느 하나라도 있으면 된다는 것을 의미하고, 가령 1 + 3처럼 2가 없어도 됨을 의미한다. 2, 3의 합으로 표현한 경우의 수라는 것은, 2, 3 중 어느 하나라도 있으면 된다는 것을 의미하고, 가령 2 + 2처럼 3이 없어도 됨을 의미하며 1은 있어서는 안 된다. 3의 합으로 표현한 경우의 수는 3만 있어야 된다는 것을 의미하고, 1, 2는 있어서는 안 된다.)

 

그 근거는 무엇인가 ? 이를 같이 살펴보도록 해보자.

먼저 근거를 3단계로 나눠서, (N - 1)을 1, 2, 3의 합으로 표현한 경우의 수 / (N - 2)를 2, 3의 합으로 표현한 경우의 수 / (N - 3)을 3의 합으로 표현한 경우의 수로 나눠서 분석해볼 것이다.

 

1. (N - 1)을 1, 2, 3의 합으로 표현한 경우의 수

 

이를 증명하는 데에는 N = (N - 1) + 1 에서 출발한다. N - 1에 1을 더하기만 하면 되기 때문에, (N - 1)을 1, 2, 3의 합으로 표현한 경우의 수를 모두 그대로 가져와 1을 더해주기만 하면 된다. 그러면 우리는 (N - 1)에서 N으로 만들어주기 위해 +1을 해준 셈이 된다.

 

2. (N - 2)를 2, 3의 합으로 표현한 경우의 수

 

사실 마찬가지로 N = (N - 2) + 2에서 출발하는데, (N - 2)를 2, 3의 합으로만 표현하고 1은 포함되어서는 안 되는 이유는 간단하다. 1이 포함된 경우는 1번 경우, 즉 (N - 1)을 N으로 만드는 과정에서 이미 세어버렸기 때문이다. 즉, 중복된다는 문제가 발생하므로 (N - 2)를 2와 3의 합으로 표현된 경우의 수 모두를 그대로 가져와 2를 더해주기만 하는 것이다.

 

3. (N - 3)을 3의 합으로 표현한 경우의 수

 

2번 경우를 완전히 이해했다면 3번 경우를 이해하는 것이 어렵지 않을 것이다. 1번 경우와 2번 경우를 통해 우리는 N을 1과 2가 포함된 덧셈식으로 구하는 방법을 모두 구해냈다. 남은 것은 3만 포함된 덧셈식을 구하는 것이기 때문에, (N - 3)을 3의 합으로만 표현한 경우의 수 모두를 그대로 가져와 3을 더해주기만 하는 것이다.

 

말로 풀어쓰니까 더 어려운 것 같기도 한데, 이를 코드로 살펴보자.

 

코드

#include <iostream>

using namespace std;

int t, n;
int dp[10001][4];
int result;

void initDpArray() {
    // dp[i][1] + dp[i][2] + dp[i][3] == i를 1, 2, 3의 합으로 표현하는 경우의 수
    // dp[i][1] : i를 1, 2, 3의 합으로 표현하되, 1을 포함해도 되는 경우의 수 (2, 3을 포함해도 됨)
    // dp[i][2] : i를 2, 3의 합으로 표현하고, 1을 포함하면 안 되는 경우의 수 (2, 3을 포함해도 되지만 1을 포함하면 안 됨)
    // dp[i][3] : i를 3의 합으로 표현하고, 1, 2를 포함하면 안 되는 경우의 수 (3을 포함해도 되지만 1, 2를 포함하면 안 됨)

    // N = 1 대한 정보 초기화
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[1][3] = 0;

    // N = 2에 대한 정보 초기화
    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[2][3] = 0;

    // N = 3에 대한 정보 초기화
    dp[3][1] = 2;
    dp[3][2] = 0;
    dp[3][3] = 1;
}

void getInput() {
    cin >> n;
}

void solve() {
    initDpArray();

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

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

void printResult() {
    cout << result << "\n";
}

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

    cin >> t;
    while (t--) {
        result = 0;
        getInput();
        solve();
        printResult();
    }

    return 0;
}

 

코드 설명

문제를 푸는 로직, 즉 

 

dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3];

dp[i][2] = dp[i - 2][2] + dp[i - 2][3];

dp[i][3] = dp[i - 3][3];

 

이 부분을 이해했다면 문제를 이해한 것이나 다름없다. 그리고 이에 대한 설명은 위에서 했기 때문에, 그리고 코드의 주석에 설명했기 때문에 이 부분에 대한 설명은 그만하기로 하고, 초기값을 설정해주는 부분만 약간의 설명을 해보겠다.

 

void initDpArray() {
    // dp[i][1] + dp[i][2] + dp[i][3] == i를 1, 2, 3의 합으로 표현하는 경우의 수
    // dp[i][1] : i를 1, 2, 3의 합으로 표현하되, 1을 포함해도 되는 경우의 수 (2, 3을 포함해도 됨)
    // dp[i][2] : i를 2, 3의 합으로 표현하고, 1을 포함하면 안 되는 경우의 수 (2, 3을 포함해도 되지만 1을 포함하면 안 됨)
    // dp[i][3] : i를 3의 합으로 표현하고, 1, 2를 포함하면 안 되는 경우의 수 (3을 포함해도 되지만 1, 2를 포함하면 안 됨)

    // N = 1 대한 정보 초기화
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[1][3] = 0;

    // N = 2에 대한 정보 초기화
    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[2][3] = 0;

    // N = 3에 대한 정보 초기화
    dp[3][1] = 2;
    dp[3][2] = 0;
    dp[3][3] = 1;
}

1을 1, 2, 3의 합으로 표현하는 방법은 1 = 1 하나 뿐이다. 그러므로 1이 포함된 덧셈식 하나이므로 dp[1][1] = 1이 되고, 1 없이 2와 3으로만 구성된 덧셈식이 0개이므로 dp[1][2] = 0이 되며, 1, 2 없이 3으로만 구성된 덧셈식이 0개이므로 dp[1][3] = 0이 된다.

 

 

2를 1, 2, 3의 합으로 표현하는 방법은 2 = 1 + 1 = 2 둘 뿐이다. 그리고 1 + 1은 1이 포함되므로 dp[2][1]에 해당되어 dp[2][1] = 1이 되고, 2는 1이 포함되지 않았으므로 dp[2][2] = 1이 되며 3으로만 구성된 덧셈식은 없으므로 dp[2][3] = 0이 된다.

 

3을 1, 2, 3의 합으로 표현하는 방법은 3 = 1 + 1 + 1 = 1 + 2 = 3 셋 뿐이다. 그리고 1 + 1 + 1과 1 + 2는 1이 포함되므로 dp[3][1] = 2가 되고, 1 없이 2와 3으로만 구성된 덧셈식은 0개이므로 dp[3][2] = 0이 되고,  1, 2 없이 3으로만 구성된 덧셈식은 3 1개이므로 dp[3][3] = 1이 된다.

 

뭔가 내 머리로는 말끔히 정리가 됐는데, 말로 전달하는 게 서툰 것 같다. 내 생각을 말로 잘 전달해보고자 블로그를 시작한 것도 있는데, 아직 노력이 더 필요한 것 같다.