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

9095번: 1, 2, 3 더하기 (acmicpc.net)

9095번: 1, 2, 3 더하기

---

DP니까 규칙을 찾아봅시당

n=1 일 때, 1가지 1

n=2 일 때, 2가지 1 + 1 = 2

n=3 일 때,  4가지 1+1+1 = 1+2 = 2+1 = 3

n=4 일 때, 7가지 1+1+1+1 = 1+1+2 = 1+2+1 = 2+1+1 = 2+2 = 1+3 = 3+1

n=5 일 때, 13가지 1+1+1+1+1 =

1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 =

1+2+2 = 2+1+2 = 2+2+1  = 

1+1+3 = 1+3+1 = 3+1+1 = 

2+3 = 3+2

 

점화식이 T(n) = T(n-1) + T(n-2)+T(n-3)인 것 같다

확인하기 위해 예제 출력에서 T(7) = 44가 나오는지 확인해본다

 

위 점화식이 맞다면

T(6) = 4+7+13 = 24

T(7) = 7+13+24 = 44  => 맞다!!

 

그렇게 코드를 작성했더니 맞았당

#include <iostream>
using namespace std;

int main()
{
    int arr[11] = {0, 1, 2, 4, };
    for(int i=4; i<=10; i++){
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
    }
    
    int T, n;
    cin >>  T;

    
    for(int i=0; i<T; i++){
        cin >> n;
        cout << arr[n] << "\n";
    }

    return 0;
}