[BOJ/C++] 백준 9095번: 1, 2, 3 더하기

Planning

---

9095번: 1, 2, 3 더하기

 

오늘 풀어볼 문제는 백준 9095번, 1, 2, 3 더하기입니다. 11보다 작은 양수 n이 주어졌을 때, 1, 2, 3의 조합으로 n을 나타내는 경우의 수를 구하는 문제입니다.

 

조건	→ 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
입력	→ 첫째 줄에 테스트 케이스의 개수 T가 주어진다. → 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. → $0<n<11$
출력	→ 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력

 

문제가 말로 설명하기는 조금 어렵습니다. 아래 예시를 보고 이해해 봅시다.

 

• n=4
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

 

n이 4로 주어졌을 때, 총경우의 수는 7입니다. 이 짧은 예시에서 우리는 순서가 다르면 다른 조합으로 취급함을 알 수 있습니다. 따라서, DFS로 간단하게 문제를 해결할 수 있습니다. 그러나 조금만 더 깊게 생각해 보면 좀 더 효율적으로 문제를 풀 수 있습니다. n에 따라 모든 경우의 수를 구해봅시다. (당연히 코드를 다 짠 이후 구한 답입니다.)

 

1	2	3	4	5	6	7	8	9	10
1	2	4	7	13	24	44	81	149	274

 

여기서 n이 4인 구간부터는 아래와 같은 점화식을 따르는 것을 볼 수 있습니다.

$$cache[n]=cache[n-1]+cache[n-2]+cache[n-3]$$

따라서, 9095번 문제의 solution은 아래와 같이 표현할 수 있습니다.

 

\begin{cases} a_n=1 & \text{ if } n=1 \\ a_n=2 & \text{ if } n=2 \\ a_n=4 & \text{ if } n=3 \\ a_n=a_{n-1}+a_{n-2}+a_{n-3} & \text{ if } n \geq 4 \end{cases}

 

 

Source Code

---

• DFS

/**
 * @file q9095.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #9095, https://www.acmicpc.net/problem/9095
 * @version 0.1
 * @date 2023-03-15
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>
#include <vector>

using namespace std;

int T, n;
vector<int> output;
int case_count = 0;

void dfs(int n);

int main() {
  cin >> T;

  for (int index = 0; index < T; index++) {
    cin >> n;
    dfs(n);
    output.push_back(case_count);
    case_count = 0;
  }
  for (int index = 0; index < T; index++) cout << output[index] << '\n';
}

void dfs(int n) {
  if (n == 0) {
    case_count++;
    return;
  } else if (n < 0)
    return;
  else {
    for (int sub = 1; sub <= 3; sub++) dfs(n - sub);
  }
}

• DP

/**
 * @file q9095.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #9095, https://www.acmicpc.net/problem/9095
 * @version 0.1
 * @date 2023-03-15
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>
#include <vector>
#define MAX 11

using namespace std;

int T, n[MAX],
    cache[MAX] = {
        0,
};

int DP(int target);

int main() {
  cin >> T;
  for (int index = 0; index < T; index++) {
    cin >> n[index];
    cout << DP(n[index]) << '\n';
  }
}

int DP(int target) {
  if (target == 1)
    return 1;
  else if (target == 2)
    return 2;
  else if (target == 3)
    return 4;
  else if (cache[target] != 0)
    return cache[target];
  else {
    return DP(target - 1) + DP(target - 2) + DP(target - 3);
  }
}

 

ChatGPT

---

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;

    // 각 테스트 케이스마다
    while (T--) {
        int n;
        cin >> n;

        // DP 배열 초기화
        vector<int> dp(n+1);
        dp[0] = 1; // 0을 나타내는 방법은 아무것도 선택하지 않는 것 1가지

        // DP 배열 계산
        for (int i = 1; i <= n; i++) {
            if (i-1 >= 0) dp[i] += dp[i-1];
            if (i-2 >= 0) dp[i] += dp[i-2];
            if (i-3 >= 0) dp[i] += dp[i-3];
        }

        cout << dp[n] << '\n';
    }

    return 0;
}

 

위 코드에서는 동적 프로그래밍을 활용하여 각 n에 대한 답을 미리 계산하여 저장한 후 출력하는 방식으로 문제를 해결한다. 동적 프로그래밍은 큰 문제를 작은 문제로 나누어 해결하는 방식으로, 중복되는 부분 문제를 해결함으로써 시간 복잡도를 줄이는 방법이다.
위 코드에서는 DP 배열을 이용하여 n을 1, 2, 3의 합으로 나타내는 방법의 수를 계산한다. dp[i]는 i를 1, 2, 3의 합으로 나타내는 방법의 수를 의미한다. 이때, dp[0]은 0을 나타내는 방법은 아무것도 선택하지 않는 것 1가지이다. 나머지 dp[i]는 i-1, i-2, i-3을 각각 1, 2, 3과 더하여 i를 만들 수 있는 방법의 수를 더한 값이 된다. 이를 모든 n에 대해 계산하여 출력하면 된다.

 

Reference

---

GitHub - YoungJ-Baek/algorithm-study