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

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

9095번: 1, 2, 3 더하기

 

dp문제다.

dp문제는 점화식을 찾으면 금방끝난다.

 

한 30분쯤 고민하다가 사고가막혀 질문게시판에 힌트보고 풀엇다(ㅜㅜ,,)

 

이 문제의 점화식은 다음과 같다.

f(n) = f(n-1) + f(n-2) + f(n-3)

 

입력 받은 값에 1,2,3 을 각각 더해주면 된다. 내가 왜 이걸 처음 보고 납득하기 힘들었냐면, 이 문제의 경우 '1+3' 과 '3+1'을 다른 것이라고 인식했기 때문이다.

그러나 손으로 몇가지의 경우를 써보면 중복되거나 놓치는 경우는 일어나지 않음을 발견하게 된다.

 

파이팅~!

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> v;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int dp[12];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    int tc;
    cin >> tc;
    while (tc--)
    {

        int n;
        cin >> n;

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

        cout << dp[n] << '\n';
    }
}