[C++] 백준 2225: 합분해

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

 

합이 N이 될 수 있는 경우의 수를 구하는 문제이다!

 

이 문제를 어렵게 하는 건 다음의 사항이었다.

1. 0도 더할 수 있다.

2. 한 개의 수를 여러 번 쓸 수 있다.

 

 

 

풀이

일단 dp를 사용하면 될 것 같았다.

1차원 dp를 n에 따라 사용해볼까 했지만,

k라는 변수도 사용하려면 2차원 배열을 사용해야 될 것 같았다.

 

그래서 dp[i][j] = i개의 숫자를 사용해서 j가 되게 하는 경우의 수로 가정했다. 

 

수학 아이디어가 좋아 점화식이 파바박 나오면 좋겠지만 그렇지는 않았다.

그렇기에 일단 시뮬레이션을 돌려보기로 했다.

N = 4, K = 4로 하고 시뮬레이션을 돌려봤다.

 

K\N	1	2	3	4
1	1	1	1	1
2	2	3	4	5
3	3	6	10	15
4	4	10	20	35

 

무언가 규칙이 보이는가?

일단 K = 1일때 값이 다 1인걸로 봐서 초기값을 1로 설정해주면 좋을 것 같았다.

그 다음 N = 1일때의 값이 K의 값과 동일하므로 그 값도 초기값으로 설정하면 좋아보였다.

 

 

그럼 이제 점화식을 찾아야한다.

보통은 이전 행의 값(위쪽), 이전 열의 값(왼쪽), 이전 행과 열의 값(대각선 왼쪽 위)을 주로 보는 편인데

그 과정에서 규칙이 보였다.

 

K\N	1	2	3	4
1	1	1	1	1
2	2	3	4	5
3	3	6	10	15
4	4	10	20	35

 

여러분도 발견하였는가?

dp[i][j] = dp[i-1][j] + dp[i][j-1]으로

이전 행의 값 + 이전 열의 값을 더한 값이 dp 배열의 값이었다!!!

 

 

만약 수학적 능력이 조금 모자르다면

필자와 같이 시뮬레이션을 돌려 표를 그려놓고 점화식을 찾는 것도 좋은 것 같다.

 

i-1과 j-1에서 이전 dp 배열의 값을 참조하므로 초기값 설정이 더더욱 필요해보였다.

 

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

    for(int i = 2; i <= k; i++){
        dp[i][1] = i;
        for(int j = 2; j <= n; j++){
            dp[i][j] = ((dp[i-1][j] % INF) + (dp[i][j-1] % INF)) % INF;
        }
    }

 

그 결과인 코드이다.

N과 K가 1부터 시작했기에 초기값도 1부터 넣어주었다.

만약 0부터 시작했다면 0에도 당연히 넣어주었을 것이다.

 

 

주의할 점은 문제에서 답을 1,000,000,000으로 나눈 나머지를 출력하라고 되어있으므로

오버플로우를 방지하는 수학식으로

(A + B) % M = (A % M + B % M) % M

을 사용해주었다!

 

 

 

전체 코드는 다음과 같다!

#include <iostream>
#define INF 1000000000
using namespace std;

int dp[205][205];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin>>n>>k;

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

    for(int i = 2; i <= k; i++){
        dp[i][1] = i;
        for(int j = 2; j <= n; j++){
            dp[i][j] = ((dp[i-1][j] % INF) + (dp[i][j-1] % INF)) % INF;
        }
    }
    
    cout<<dp[k][n];
    return 0;
}