[BOJ] 2225 합분해

1. 문제 링크

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

2. 문제 해설

이 문제는 전형적인 dp문제이다. dp 테이블을 어떻게 잡느냐가 제일 핵심인데, 필자는 x축을 n, y축을 k로 놓고 문제를 풀었다.

순서대로 풀이를 해보자면

1. k가 1일 때는 모두가 자기 자신만 더하면 되는 것이므로 모두 개수가 1개이다.

2. k가 2일 때는 자신보다 x 작다면 x를 더해주면 되는 것이므로 자신보다 작은 k가 1인 값들을 전부 더해주면 자신의 값이다.

예를들어 n이 5라면

(5 + 0), (4 + 1), (3 + 2), (2 + 3), (1 + 4), (0 + 5)

이렇게 6개가 된다.

3. k가 3일 때는 자신보다 앞에서 구해놓은 k가 2일 때의 값들을 자신보다 작거나 같은 n의 값들을 전부 더해준다.

예를 들어 n이 3이고 k가 3이라면

(0 + 0) + 3, (0 + 1) + 2, (1 +0) + 2, (2 + 0) + 1, (1+ 1) + 1, (0 + 2) + 1, (3 + 0) + 0, (0 + 3) + 0, (1 + 2) + 0, (2 + 1) + 0

이렇게 10개가 나온다.

그런데 잘 보면 괄호 안의 값은 전부 k가 2일 때 n이 3보다 작거나 같은 값 들이다. 즉 k가 하나 작은 값 들에서 부족한 수를 더해주면 우리가 원하는 k의 값을 가진 n이 나온다.

표를 예시로 들어주면 아래처럼 나온다.

k \ n	0	1	2	3
1	1	1	1	1
2	1	2	3	4
3	1	3	6	10

4. 더하면서 10억으로 나머지 연산을 계속 해주면서 더한다.

이 풀이의 시간복잡도는 O(N*K) 이다.

3. 소스코드

#include<iostream>
#define MAXNUM 210
using namespace std;

int main(){
    int n, k;
    int dp[MAXNUM][MAXNUM]={1};
    scanf("%d %d", &n, &k);
    for (int i=1; i<=k; i++) {
        for (int j=0; j<=n; j++) {
            if (j==0) {
                dp[i][j] = 1;
                continue;
            }
            dp[i][j] += dp[i-1][j] + dp[i][j-1];
            dp[i][j] %= 1000000000;
        }
    }
    
    printf("%d\n", dp[k][n]);
    
    return 0;
}

4. 추가 언급

우리는 나머지를 구한다고 할 때, 왜 저렇게 중간에 계속 나머지 연산을 해줄까? 마지막에만 나머지 연산을 해주면 되는 것이 아닐까?

결론을 말하자면 아니다. 연산 중간에 int범위를 넘어가 버릴 수도 있기 때문이다. int범위를 넘어가면 overflow가 발생해서 이상한 값이 나올 수도 있다. 이를 방지하기 위해서 중간에 mod연산을 해주는 것이다. 10억으로 mod연산을 하면 두 수를 더하더라도 int범위를 넘어가지 않으므로 덧셈을 하는 데에 문제가 되지 않는다.

mod 연산은 덧셈, 뺄셈에 있어서 분배법칙이 성립하기 때문에 다른 문제를 풀 때도 확인을 하기 위해서 중간에 mod연산을 해주어도 아무런 문제가 되지 않는다. 자신의 코드에 확신이 있다면 굳이 연산량이 많은 mod연산을 쓸 필요는 없지만, 헷갈린다면 쓰는 것도 괜찮은 방법인 듯 하다.