백준 9095번, 1, 2, 3 더하기

백준 9095번 c++ 문제풀이

문제:

백준 9095

풀이:

1. dp문제이다.
2. dp로 풀수 있게 점화식 세운다.

3. 1= 1 = 1
   2= 1 1, 2 = 2
   3= 1 1 1, 2 1, 3 = 1+2+1 = 4
   4= 1 1 1 1, 2 2, 2 1 1, 3 1 = 1 + 1 + 3 + 2=7
   5= 1 1 1 1 1, 2 2 1, 2 1 1 1, 3 1 1, 3 2 = 1 + 3 + 4 + 3+ 2 = 13
   6= 1 1 1 1 1 1, 2 2 2, 2 2 1 1, 2 1 1 1 1, 3 1 1 1, 3 2 1, 3 3 = 1 + 1 + 6 + 5+ 4 + 6 + 1 = 24
   7= 1 1 1 1 1 1 1, 2 2 2 1, 2 2 1 1 1, 2 1 1 1 1 1, 3 1 1 1 1, 3 2 2, 3 2 1 1, 3 3 1 = 1 + 4 + 10 + 6 + 5 + 3 + 12+3 = 44
   

따라서. result[n] = result[n-1] + result[n-2] + result[n-3];
규칙을 찾는게 중요한 것 같다.

코드:

#include <iostream>
#include <algorithm>

using namespace std;

int result[12];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    result[1] = 1;
    result[2] = 2;
    result[3] = 4;

    int t;

    cin >> t;

    for(int i=0;i<t;i++){
        int num;

        cin >> num;

        for(int j=4;j<=num;j++){
            result[j] = result[j-1] + result[j-2] + result[j-3];
        }

        cout << result[num] << "\n";
    }
    return 0;
}

감사합니다.