[알고리즘] 백준 2225 - 합분해

✅ 문제

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

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

✅ 조건

시간 제한	메모리 제한
2 초	128 MB

✅ 입력

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

✅ 출력

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

✅ 풀이

중복 순열을 이용하는 방법으로 접근하고 풀이 했지만 시간초과... 그리고 다시 모든 경우를 따지면서 접근해보니 DP 문제라는 판단을 내릴 수 있었다.

 

처음에는 dp[n]을 0 ~ n 까지의 수중 k개를 뽑아서 n을 만들 수 있는 경우의 수라고 가정하고 dp 테이블을 만들었다. 하지만 dp 테이블을 1차원으로 만들었을 때 규칙을 찾을 수 없었으며, 뒤늦게 dp 배열이 이차원 형태여야 된다는 사실을 깨달았다. (n과 k를 모두 고려한 해를 찾아야 한다.)

 

이제 dp[n][k]를 0 ~ n 까지의 정수 중에서 k개를 뽑아서 n을 만들 수 있는 경우의 수라고 생각하고 다시 한번 접근해보니 규칙을 찾을 수 있었다.

 

예를 들어 dp[1][1]은 0 ~ 1 까지의 정수 중에서 1개를 뽑아서 1을 만들 수 있는 경우의 수이고 이는 직관적으로 1밖에 없으므로 dp[1][1] = 1이라는 사실을 알 수 있다.

 

예제 입력 2을 기준으로 생각해보면 n = 6, k = 4일 때 dp 테이블은 다음과 같이 구성된다. (편의를 위해 행과 열의 길이는 각각 +1을 해주었다.)

 

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0

 

첫번째 열의 모든 행들은 1이라는 사실 또한 쉽게 계산해볼 수 있다. 그리고 첫번째 열의 행은 1씩 더해지는 등차수열임을 알 수 있었다. 그렇게 dp 테이블을 구성해보면 아래와 같음을 알 수 있다.

 

0	0	0	0	0
0	1	2	3	4
0	1	0	0	0
0	1	0	0	0
0	1	0	0	0
0	1	0	0	0
0	1	0	0	0

 

그리고 규칙을 찾아보기 위해서 dp[2][2]와 , dp[2][3] 까지만 직접 구해보기로 했다.

dp[2][2]는 0~2 까지의 정수에서 2가지를 뽑아서 2를 만드는 경우의 수이므로..

 

1. 0 + 2
2. 2 + 0
3. 1 + 2

 

3가지의 경우가 있음을 알아냈다. 그러므로 dp[2][2] = 3이다.

dp[2][3]은 0~2 까지의 정수에서 3가지를 뽑아서 2를 만드는 경우의 수이므로..

 

1. 0 + 0 + 2
2. 0 + 2 + 0
3. 2 + 0 + 0
4. 1 + 1 + 0
5. 1 + 0 + 1
6. 0 + 1 + 1

 

위와 같이 6가지가 있음을 알아냈다. 그러므로 dp[2][3] = 6일 것이고, 현재 테이블은 다음과 같을 것이다.

 

0	0	0	0	0
0	1	2	3	4
0	1	3	6	0
0	1	0	0	0
0	1	0	0	0
0	1	0	0	0
0	1	0	0	0

 

위와 같이 결과가 적은 경우들을 직접 구해서 dp 테이블을 채워나가다 보니 dp[i][j] = dp[i][j-1] + dp[i-1][j] 이라는 점화식을 도출해낼 수 있었다.

 

점화식이 확실한지? dp[2][4]를 한번 더 직접 구해본다면..

 

1. 0 + 0 + 0 + 2
2. 0 + 0 + 2 + 0
3. 0 + 2 + 0 + 0
4. 2 + 0 + 0 + 0
5. 1 + 1 + 0 + 0
6. 1 + 0 + 1 + 0
7. 1 + 0 + 0 + 1
8. 0 + 1 + 1 + 0
9. 0 + 0 + 1 + 1
10. 0 + 1 + 0 + 1

 

위와 같이 10가지가 있음을 알아냈고 점화식을 올바르게 도출해낸 것을 알 수 있었다.

점화식을 바탕으로 dp[n][k] % 100000000을 출력하면 된다. 풀이 코드는 아래와 같다.

 

from sys import stdin as s

if __name__ == "__main__":
    n, k = map(int, s.readline().rstrip().split())

    # dp[k][n] = 0 ~ n 개의 수 중에서 정수 k개를 더해서 n이 되는 경우의 수
    dp = [[0] * (k+1) for _ in range(n+1)]

    for i in range(1, n + 1):
        dp[i][1] = 1

    for i in range(1, k + 1):
        dp[1][i] = i      
    
    for i in range(2, n+1):
        for j in range(2, k+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    print(dp[n][k] % 1000000000)

 

계산 실수만 안했더라면 내 힘으로 풀어낼 수 있는 문제였던터라 많이 아쉽다.

하지만 DP문제에 조금씩 익숙해지는 것 같다. 꾸준히 풀어가야겠다.