[C++] BOJ 9095 1, 2, 3 더하기

 

 

문제 출처

백준 온라인 저지

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

9095번: 1, 2, 3 더하기

 

문제 

 

문제 입 / 출력

 

풀이

DP를 활용해서 푼다

• 정수 1을 나타내는 방법은 1가지이다.
• 정수 2를 나타내는 방법은 2 ( 1+1, 2) 가지이다.
• 정수 3을 나타내는 방법은 4 ( 1+1+1, 2+1, 1+2, 3) 가지이다.

위를 토대로 점화식을 세우면

$$ {a_{i}}^{} = {a_{i-1}}^{} + {a_{i-2}}^{} + {a_{i-3}}^{}  $$

와 같은 결과를 얻을 수 있다.

 

 

코드

#include <iostream>

using namespace std;

int dp[100001][11] = {};
int main() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) {
    int n;
    cin >> n;
    dp[n][1] = 1;
    dp[n][2] = 2;
    dp[n][3] = 4;
    for (int i = 4; i <= n; i++) {
      dp[n][i] = (dp[n][i - 1] + dp[n][i - 2] + dp[n][i - 3]) % 10007;
    }
    cout << dp[n][n] << "\n";
  }
}