[백준] 9095번: 1, 2, 3 더하기

 

 

---

 

문제

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

 

 

 

 

 

실행 결과

 

 

 

 

 

코드(c++)

#include <iostream>
using namespace std;

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

  int t;
  cin >> t;

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

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

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

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

  return 0;
}

 

 

 

 

코드 설명

11까지라고 주어졌으므로 미리 12의 크기를 가진 배열 dp를 선언한다. (0~11)

1, 2, 3 각각의 숫자에 대하여 1,2,3으로 만들 수 있는 합의 가짓수를 구하고, 배열 dp에 저장한다.

 

1 = 1 => 1개

따라서 dp[1]=1

 

2 = 1+1 = 1 => 2개

따라서 dp[2]=2

 

3 = 1+1+1 = 1+2 =2+1=3 => 4개

따라서 dp[4]=2

 

4부터 11까지는 1, 2, 3의 가짓수만 이용해서 구하면 되므로 점화식을 세워서 계산한다!

아주 기초적인 다이나믹 프로그래밍 문제..!

 

---