_9764 - 서로 다른 자연수의 합

점화식만 잘 이해하면 된다.

//C++
#include <iostream>

using namespace std;
int dp[2010][2010] = { 0 };
int tcs[21];

int main(void) {
    int tc;
    cin >> tc;

    // Test Case Save
    int input;
    int max = -1;
    for(int i=1; i<=tc; i++) {
        cin >> input;
        tcs[i] = input;
        if (input > max) {
            max = input;
        }
    }
    // Initialize
    dp[0][0] = 1;
    for(int i=1; i<=max; i++){
        dp[0][i] = 1;
        dp[i][0] = 0;
    }
    
    //for - loop , memoization
    for(int i = 1; i <= max; i++){
        for(int j = 1; j <= max; j++) {
            if(i < j) {
                dp[i][j] = dp[i][j-1];
            } else {
                dp[i][j] = (dp[i][j-1] + dp[i-j][j-1]) % 100999;
            }
        }
    }
    // Print out
    for(int i = 1; i<= tc; i++) {
        int n = tcs[i];
        cout << dp[n][n]<<endl;
    }
    return 0;
}

좀... 깔끔하게 짰다고 생각하는데 훈수두고 싶으면 댓글 달아주시오.