[백준] 15988_1, 2, 3 더하기 3 C++

11 Jan 2024 in Study on Coding Test

기초적인 DP 문제

정답제출코드

#include <iostream>

#define MOD 1000000009

using namespace std;

typedef long long ll;

int N;
ll DP[1000001];

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

    cin >> N;

    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 4;
    
    for (int i = 4; i <= 1000000; ++i)
        DP[i] = (DP[i-1] + DP[i-2] + DP[i-3]) % MOD;

    for (int i = 0; i < N; ++i)
    {
        int _input;
        cin >> _input;

        cout << DP[_input] % MOD << '\n';
    }


    return 0;
}

우선 경우의 수를 일일이 세어보면

• N = 1 : 1
• N = 2 : 2
• N = 3 : 4
• N = 4 : 7
• N = 5 : 13
• N = 6 : 24 …

이렇게 된다.

여기서, N >= 4일때, 아래와 같은 점화식이 세워진다.

DP[i] = DP[i-1] + DP[i-2] + DP[i-3]

이렇게 해서 저장해주면 끝이다.

다만, 이문제는 1000000009로 나눈 나머지를 출력하라고 했으니 저장할 때 나머지 연산을 사용해주도록 하자.