[BOJ] 백준 2225 합분해 (문제 설명, 코드, C++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 백준의  2225번 합분해 문제입니다.

 

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

 

0부터 N까지의 정수 중 K개를 뽑아 더하고 그 결과가 N이 되는 경우의 수를 찾아야합니다.

덧셈의 순서가 다른 경우엔 다른 경우로 셉니다. 한 개의 수를 중복적으로 사용가능합니다. 

 

 

 

 

해결 과정

 

0에서 3 까지 수에서 2개를 뽑아 합이 3인 경우의 수는

3을 하나 뽑았다는 가정하에 0에서 0 까지의 수 중 1개를 뽑아 합이 0이 되는 경우를 포함합니다.

- 0 3

2를 하나 뽑았다는 가정하에는 0에서 1 까지의 수 중 1개를 뽑아 합이 1이 되는 경우를 포함합니다.

- 1 2

1을 하나 뽑았다는 가정하에는 0에서 2 까지의 수 중 1개를 뽑아 합이 2가 되는 경우를 포함합니다.

- 2 1

0을 하나 뽑았다는 가정하에는 0에서 3 까지의 수 중 1개를 뽑아 합이 3이 되는 경우를 포함합니다.

- 3 0

 

다음과 같은 점화식을 유도할 수 있습니다.

 

dp[i][j] = dp[i][j] + dp[0 ~ i][j-1]

 

 

코드 전문

 

 

#include <iostream>
#include <algorithm>

using namespace std;

const int MOD = 1'000'000'000;

int dp[202][202];
int n, k;

int main() {
    cin >> n >> k;

    for (int i = 0 ; i <= 201; ++i) {
        dp[0][i] = 1;
    }

    for (int i = 1 ; i <= 201; ++i) {
        for (int j = 1 ; j <= 201; ++j) {
            for (int m = 0; m <= i; ++m) {
                dp[i][j] = (dp[i][j] + dp[m][j-1]) % MOD; 
            }
        }
    }

    cout << dp[n][k];
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

DP 많이 풀고 무럭무럭 자라고싶네요.

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.