https://www.acmicpc.net/problem/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);
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 1676번 C++ 풀이 (0) | 2022.03.21 |
---|---|
백준 2729번 C++ 풀이 (0) | 2022.03.21 |
백준 10610번 C++ 풀이 (0) | 2022.03.18 |
백준 14501번 C++ 풀이 (0) | 2022.03.13 |
백준 1010번 C++ 풀이 (0) | 2022.03.09 |