[알고리즘 문제 풀이][DP] 백준 2225번 - 합분해

백준 2225번 합분해 문제입니다.

(DP)

 

- 문제 설명: https://www.acmicpc.net/problem/2225

- 문제 풀이:

 

본 문제는 최종 합을 만들기 위해 분해하는 문제이므로, DP 점화식이 필요합니다.

DP 점화식을 도출하는 것이 어려운데, 잘 설명한 글이 있어 참고하였습니다.

(https://mygumi.tistory.com/135 또는 https://hongjw1938.tistory.com/63)

 

K 개의 숫자를 이용하여 N 이라는 숫자를 만드는 경우의 수 (DP[K][N]) 를 구하는 문제입니다.

N 을 만들기 위해서는 1개의 숫자 A 가 합해졌다면, 나머지 K-1개의 숫자로는 (총 K개의 숫자를 사용해야하므로) N-A 값을 만들어야합니다.

 

위의 점화식을 구체적으로 보기에 앞서, 경우의 수를 직접 따져보면 다음과 같습니다.

문제에 따르면 숫자 0 부터 N 까지 사용할 수 있고, 순서가 다르면 다른 경우로 간주합니다.

	N=0	N=1	N=2	N=3	N=4
K=1	1개 0	1개 1	1개 2	1개 3	1개 4
K=2	1개 0, 0	2개 0, 1 1, 0	3개 0, 2 2, 0 1, 1	4개 0, 3 3, 0 1, 2 2, 1	5개 0, 4 4, 0 1, 3 3, 1 2, 2
K=3	1개 0, 0, 0	3개 0, 0, 1 0, 1, 0 1, 0, 0	6개 0, 0, 2 0, 2, 0 2, 0, 0 0, 1, 1 1, 1, 0 1, 0, 1	10개 0, 0, 3 0, 3, 0 3, 0, 0 0, 1, 2 1, 2, 0 1, 0, 2 0, 2, 1 2, 1, 0 2, 0, 1 1, 1, 1	15개 0, 0, 4 0, 4, 0 4, 0, 0 0, 1, 3 1, 3, 0 1, 0, 3 0, 3, 1 3, 1, 0 3, 0, 1 0, 2, 2 2, 2, 0 2, 0, 2 1, 1, 2 1, 2, 1 2, 1, 1
K=4		...	...	...	...

만약에 숫자 2개를 사용하여 2 를 만드는 경우의 수를 따진다면 (DP[K=2][N=2]),

K-1 (=1개) 로 0을 만드는 경우, K-1 (=1개) 개로 1을 만드는 경우, K-1 (=1개) 개로 2를 만드는 경우를 모두 고려해야합니다. 0 을 만들었다면 2를 더하면 2가 되고, 1을 만들었다면 1을 더하면 2가 되고, 2를 만들었다면 0을 더하면 2가 되므로, 세 경우를 모두 합하면 됩니다.

 

따라서 DP[2][2] = DP[1][0] + DP[1][1] + DP[1][2] 이렇게 구할 수 있습니다.

표에서 보면, 파란색 3칸의 합이 아래 분홍색 한 칸의 값이 되는 것입니다. 이런 식으로 표를 쭉 채워나가면 마지막에 얻는 DP[K][N] 으로 문제의 답을 구할 수 있습니다.

	N=0	N=1	N=2	N=3	N=4
K=1	1개	1개	1개	1개	1개
K=2	1개	2개	3개	4개	5개
K=3	1개	3개	6개	10개	15개
K=4		...	...	...	...

 

- 코드: 

// 버전 1 - 3중 포문 해 (C/C++ 언어)
for(int i=0;i<=n;i++)
	dp[1][i] = 1;

for(int i=1;i<=k;i++)
	for(int j=0;j<=n;j++)
		for(int l=0;l<=j;l++)
			dp[i][j] += dp[i-1][j-l];

// 코드 출처: https://mygumi.tistory.com/135

전체의 합을 일일히 다 구하려면 위와 같이 3중 포문으로 구현을 할 수 있습니다.

그러나 사실 위의 표에 더해지는 것을 잘 보면 전체를 다 더 할 필요가 없다는 것을 발견할 수 있습니다.

	N=0	N=1	N=2	N=3	N=4
K=1	1개	1개	1개	1개	1개
K=2	1개	2개	3개	4개	5개
K=3	1개	3개	6개	10개	15개
K=4		...	...	...	...

DP[K][N] (분홍색) 값을 구할 때는 DP[K][N-1] (왼쪽 파란색) 과 DP[K-1][N] (위쪽 파란색) 의 합으로 구할 수 있습니다. 왜냐하면 DP[K][N-1] (왼쪽 파란색) 자체가 이미 DP[K-1][0] 부터 DP[K-1][N-1] 까지의 합 (이전 표에서 위쪽 파란색) 을 반영한 것이기 때문에, 그 값을 바로 더해줘도 되는 것입니다.

 

이렇게 수정하면 다음과 같이 코드를 쓸 수 있습니다. 3중 포문이 2중 포문으로 줄어든 것을 볼 수 있습니다.

# 버전 2 - 2중 포문 해 (Python)
N, K = map(int, input().split())

dp = [[1 for i in range(N+1)] for j in range(K+1)]

for i in range(2,K+1):
    for j in range(1,N+1):
        dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000000

print(dp[K][N])

 

 

- 실수 포인트 & 반례:

1. 본 문제는 별다른 반례가 없습니다.