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

문제 :

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

분석 :

점화식을 세우면 간단히 해결할 수 있는 문제였다!

큰 문제가 작은 문제로 나누어지는 전형적인 dp 문제였고 

1, 2, 3의 합으로 나타낸다는 것은 

 

1일때

1

 

2일때 

1 + 1

2

 

3일때 

1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

1 + 1 + 2

1 + 3

 

과 같이 나타내어지는 것을 의미한다. 

n = 4일 경우 나타내어지는 경우의 수를 memo[4]라고 하자

그럴때 경우의 수는 

1 + memo[3]

2 + memo[2]

3 + memo[1] 

일 것이다. 

 

따라서 점화식은 memo[n] = memo[n-1] + memo[n-2] + memo[n-3]과 같이 나타내어진다.

 

 

c++ 코드 :

//
//  9095_123plus.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/05/04.
//

#include <stdio.h>
#include <iostream>
using namespace std;
int dp[11] = {0, };
int memo[11] = {0, };

int dp_plus(int n){
    if(memo[n] > 0){
        return memo[n];
    }else{
        memo[n] = dp_plus(n - 1) + dp_plus(n - 2) + dp_plus(n - 3);
        return memo[n];
    }
}

int main(){
    int TC;
    cin >> TC;
    memo[1] = 1; memo[2] = 2; memo[3] = 4;
    for(int i =0; i < TC; i++){
        int n;
        cin >> n;
        int dpResult = dp_plus(n);
        cout << dpResult << '\n';
    }
  
    return 0;
}