서로 다른 자연수의 합 (백준 9764)

안녕하세요. 오늘은 자연수의 합 문제를 풀 거예요.

문제

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

아이디어

dp[x][y]를 x를 만드는데 맨 마지막 수를 y로 쓸 때 경우의 수 입니다.
sum[x][y]는 dp[x][0]부터 dp[x][y]까지의 합 입니다.
이를 통해서 dp값을 갱신해주면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll dp[2020][2020] = { 0 }, sum[2020][2020] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll i, j, k;
    for (i = 1; i <= 2000; i++)
    {
        for (j = 1; j < i; j++)
        {
            dp[i][j] = sum[i - j][j - 1];
            sum[i][j] = (dp[i][j] + sum[i][j - 1])%100999;
        }
        dp[i][i] = 1;
        sum[i][i] = (sum[i][i - 1] + 1)%100999;
        for (j = i + 1; j <= 2000; j++) sum[i][j] = sum[i][j - 1]; //빈공간 채워주기
    }

    ll T, N;
    cin >> T;
    while (T--)
    {
        cin >> N;
        cout << sum[N][N] << "\n";
    }
}

감사합니다.