[백준 9095] 1, 2, 3 더하기 (C#, C++) - soo:bak

문제 링크

9095번 - 1, 2, 3 더하기

설명

양수 n (1 ≤ n < 11)을 1, 2, 3의 합으로 표현하는 방법의 수를 구하는 문제입니다.

같은 수를 여러 번 사용할 수 있으며, 합을 이루는 순서가 다르면 다른 방법으로 인정합니다.

예를 들어 4는 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2, 1 + 3, 3 + 1 총 7가지 방법으로 만들 수 있습니다.

접근법

동적 프로그래밍을 사용하여 해결합니다.

n을 만드는 방법은 마지막에 더한 수에 따라 세 가지 경우로 나눌 수 있습니다.

마지막에 1을 더한 경우, 그 이전까지는 n - 1을 만드는 방법이었으므로 dp[n - 1]가지입니다.

마찬가지로 마지막에 2를 더한 경우는 dp[n - 2]가지, 마지막에 3을 더한 경우는 dp[n - 3]가지입니다.

따라서, dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]의 점화식이 성립합니다.

기저 값은 dp[1] = 1, dp[2] = 2, dp[3] = 4로 설정하고, 이를 바탕으로 dp[4]부터 dp[10]까지 미리 계산해 둡니다.

n의 최댓값이 10으로 작으므로, 모든 테스트 케이스를 배열에서 바로 찾아 답할 수 있습니다.

---

Code

C#

using System;
using System.Linq;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var dp = new int[11];
      dp[1] = 1;
      dp[2] = 2;
      dp[3] = 4;
      
      for (var i = 4; i <= 10; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

      var t = int.Parse(Console.ReadLine()!);
      foreach (var _ in Enumerable.Range(0, t)) {
        var n = int.Parse(Console.ReadLine()!);
        Console.WriteLine(dp[n]);
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

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

  int dp[11] = {};
  dp[1] = 1;
  dp[2] = 2;
  dp[3] = 4;

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

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    cout << dp[n] << "\n";
  }

  return 0;
}