백준 9764번 서로 다른 자연수의 합 [C++]

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

 

 

 

#문제 간단 정리

 

#문제 해결 방법

 

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 

 

일단 해결로직은 저렇긴한데

dp를 떠올리는 발상을 정리해보자면 

일단 특정 숫자를 쓰냐 안쓰냐로 생각 할 수 있고

j를 안쓰고 만들면 j-1 개를 가지고 만드는 가지수와 같고

j까지의 숫자를 써서 N을 만드는 방법은 = j-1 까지의 숫자를  써서 N-j 을 만들는 방법 + j를 안쓰고 만드는 방법으로 나눌수 있다

 

때문에 i 를 j 개의 숫자를 써서 만드는

dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수 를 떠올리면 된다

 

#전체 코드

 

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
#define MOD 100999

int dp[2001][2001];

int main() {

    int t;
    int n;

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 


    dp[0][0] = 1;
    for (int i = 1; i < 2001; i++) {
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for (int i = 1; i < 2001; i++) {
        for (int j = 1; j < 2001; j++) {
            dp[i][j] = dp[i][j - 1];  //j를 포함하지 않고 i를 만드는 경우
            if (i >= j) {
                dp[i][j] += dp[i - j][j - 1];
                dp[i][j] %= MOD;
            }
        }
    }

    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n][n] << endl;
    }


    return 0;
}