백준/15989번/1,2,3 더하기 4/골드5

Problem Link: https://www.acmicpc.net/problem/15989

문제 설명

Site: Baekjoon
Name: 1,2,3 더하기 4 Category: Dynamic Programming Rank: Gold 5

각 숫자를 1, 2, 3의 합으로 만들 수 있는 방법의 갯수를 구하는 문제. 중복은 불가능하다.

문제 풀이

1. 모든 숫자는 1만으로 만들 수 있는 방법이 1개.

2. 1만으로 만든 방법에 2를 더해서 만드는 방법을 추가.

3. 1과 2로 만드는 방법에 3을 더해서 만드는 방법을 추가하면 정답이 나온다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[10001];

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

    std::fill_n(arr, 10001, 1);

    for (int i = 2; i < 10001; ++i)
    {
        arr[i] += arr[i - 2];
    }

    for (int i = 3; i < 10001; ++i)
    {
        arr[i] += arr[i - 3];
    }

    int n = 0;
    cin >> n;

    vector<int> v;

    for (int i = 0; i < n; ++i)
    {
        int temp;
        cin >> temp;

        v.push_back(temp);
    }

    for (int i = 0; i < v.size(); ++i)
    {
        cout << arr[v[i]] << endl;
    }

    return 0;
}