1, 2, 3 더하기 9 16195

문제

접근 방법

1, 2, 3 더하기 7을 변형한 문제이다.
이하라는 것은 해당 개수 이하는 모두 더해주면 된다는 것이다.
해당 풀이에 값을 더해서 출력해주는 부분을 추가해주면 될 것이다.

코드

#include <iostream>
using namespace std;
long long dp[1001][1001]; // n m
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    dp[1][1] = 1; // 1
    dp[2][1] = 1; // 2
    dp[2][2] = 1; // 1+1
    dp[3][1] = 1; // 3
    dp[3][2] = 2; // 1+2 2+1
    dp[3][3] = 1; // 1+1+1
    int T, min = 4;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        for (int i = min; i <= n; ++i)
        {
            for (int j = (i - 1) / 3; j <= i; j++)
            {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 2][j - 1] + dp[i - 3][j - 1]) % 1000000009;
            }
        }
        long long ret = 0;
        for (int i = n / 3; i <= m; ++i)
        {
            ret = (dp[n][i] + ret) % 1000000009;
        }
        cout << ret << "\n";
        if (n > min)
            min = n;
    }
    return 0;
}

풀이

1, 2, 3 더하기 7에 합산하는 기능만 추가된 것이다.