백준 2225번 C++ 풀이

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

2225번: 합분해

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드5

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

중복조합 문제이다. 이게? 라고 생각할 수 있겠지만, 생각을 좀만 해보면 중복조합인 것을 쉽게 눈치챌 수 있다.

 

예제 1인 20, 2를 예시로 보자. 0부터 20까지의 정수 2개를 더해서 20이 되는 경우이다. 20이라는 숫자를 숫자로 보지 말고, 하나씩 일렬로 나열된 공이라고 생각해보자.

 

. O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . 

 

위에 점이 보일 것이다. 이 점에 우리는 막대기를 하나 끼워서 두개의 묶음으로 나눠보자. 어디에 끼워 넣더라도 두 묶음의 합은 당연히 20일 것이다. 20개의 공을 나눴으니 말이다. 맨 앞과 맨 뒤에는 끼우면 안되는거 아니냐고? 0부터 20까지의 숫자를 골라야 하니, 가능하다. 

 

예제 2로 자세히 알아보자. 0부터 6까지의 정수 4개를 더해서 6을 만드는 것이다. 똑같이 따라해보자.

 

. O . O . O . O . O . O .

 

3개의 막대기를 통해 4개의 묶음으로 만들어보자. 3개의 막대기가 맨 앞이나 맨 뒤에만 있을 수도 있고, 적절히 있을 수도 있다. 1 + 2 + 3 = 6이나, 2 + 1+ 3 = 6은 다른 경우로 세기 때문에, 이런 방식으로 접근해도 되는 것이다.

 

고등학교에서 경우의 수를 배웠다면, 이러한 증명방법은 본 적이 있을 것이다. 그렇다. 교과서에서 중복조합에 대해 소개할 때 이런 방식을 많이 채용한다.

 

결국 이 문제를 한줄로 요약하면 다음과 같다.

n + 1개에서 중복을 포함하여 순서없이 r - 1개를 고르는 경우의 수

 

그리고 이는 (n + 1)H(r - 1)이고, 조합으로 바꿔보면 (n + r - 1)C(r - 1)이다.

 

결국 이 문제는 입력하는 숫자가 조금만 커져도 값이 기하급수적으로 커지는 팩토리얼 연산으로 구성된 조합을 어떻게 처리할 것이냐를 의도하는 문제라고 볼 수 있다.

 

dp를 통해 처리하자. 이 전에 풀이했던 1010번(https://codejin.tistory.com/172)에서 첫번째로 사용한 방법을 가져오자. 다만 숫자가 매우 커지기 때문에, 문제에서도 1,000,000,000으로 나눈 나머지만을 요구한다. 숫자가 커지지 않게 모듈러 연산(https://codejin.tistory.com/68)을 계속 수행하면서, 조합을 계산해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000000

array<array<int, 401>, 401> memo;

int solution(int n, int r) {
    if (memo[n][r]) return memo[n][r];
    else{
        memo[n][r] = (solution(n - 1, r - 1) % mod + solution(n - 1, r) % mod) % mod;
        return memo[n][r];
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i = 0; i < 201; i++) { // memo array init
        memo[i][0] = memo[i][i] = 1;
    }

    int n, r;
    cin >> n >> r;
    cout << solution(n + r - 1, r - 1);
}