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

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

기본적인 DP 문제입니다.

 

1 → 1개 / 1

2 → 2개 / 1 + 1, 2

3 → 4개 / 1 + 1 + 1, 1 + 2, 2 + 1, 3

4 → 7개 / 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2, 1 + 3, 3 + 1

 

여기서 잘 보시면 4의 경우 1에 3을 더하는 경우, 2에 2를 더하는 경우, 3에 1을 더하는 경우로 이루어져 있습니다.

 

1에 3을 더하는 경우 → 1 + 3

2에 2를 더하는 경우 → 1 + 1 + 2, 2 + 2

3에 1을 더하는 경우 → 1 + 1 + 1 + 1, 1 + 2 + 1, 2 + 1 + 1, 3 + 1

 

총 7가지의 경우의 수로 n이 4 이상일 때,

 

$DP[n] = DP[n - 1] + DP[n - 2] + DP[n - 3]$의 점화식을 도출해낼 수 있습니다.

 

#include<iostream>

using namespace std;

int DP[11];

int main(void)
{
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 4;

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

    int t; cin >> t;

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

    return 0;
}

반례

Input

5

Output

13

 

Input

6

Output

24

 

Input

8

Output

81

 

Input

9

Output

149