백준 9095 1, 2, 3 더하기 c++ [컴공과고씨]

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

9095번: 1, 2, 3 더하기

문제를 보고 규칙이 있을 것 같아서 쭉 써보았다. 

1 -> 1개

2 -> 2개

3 -> 4개

4 -> 7개

5 -> 13개

여기서 점화식을 알아낼 수 있는데 n = (n-1) + (n-2) + (n-3)번째 라는 점화식을 볼 수 있었다.

점화식은 다이나믹 프로그래밍으로 풀면 쉽게 풀 수 있어 다이나믹 프로그래밍을 이용하여서 문제를 풀었다.

 

단계별 문제 풀이

1. dp 배열 선언 

2. 초기값 dp[1], dp[2], dp[3] 값 입력

3. 점화식을 이용해서 풀어줌

 

 

전체코드

#include <iostream>
using namespace std;
int main(){
    int n,t;
    cin >> t;
    while(t--){
        cin >> n;
        int dp[12];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4; // 초기값 
        for (int i = 4; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; // 점화식
        }
        cout << dp[n] << '\n';
    }
    return 0;
} // 13min

체감난이도	걸린시간	참고	사용 알고리즘
하	13min	x	다이나믹 프로그래밍 (dynamic programming)