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

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

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

2225번: 합분해

이번 문제는 조금 오래 걸렸다. 한시간이 안되게 걸리긴 했지만 그래도 DP인 것을 알고 풀어서 그나마 나았지.. 몰랐으면 고생을 조금 더 했을 것 같다.

 

풀이를 적었는데 앞부분은 너무 두서없는 것도 같고 뒤에 갈수록 이해는 될 것 같기도 하고..

 

이번 문제는 0부터 N까지 K개의 수를 더해서 N을 만드는 문제이다. 여기서 중요한 것은 강조한 것처럼 "0부터"라는 것이다. 예시에서 주어진 문제를 살펴보면 쉽게 이해할 수 있다. 예제 입력으로 20 2 가 주어졌는데, 2개의 수를 더해서 20을 만드는 경우는 아래의 경우가 있고, 그래서 21개가 된다.

 

(0 + 20), (1 + 19), (2 + 18), ... (19 + 1), (20 + 0)

 

마찬가지로 3개로 20을 구하려 할 때도 (0 + 0 + 20) 과 같은 경우도 포함된다는 것이다. 그 말은 결국 0을 제외한 1부터 N까지의 수에서 K개 이하를 이용해서 N을 만들고 0을 포함시켜 조합을 하면 된다..! 고 처음에 생각했으나 코드가 복잡해질게 눈에 훤했다.

 

 

 

그래서 예제를 작게 잡고 다시 찬찬히 생각해보았다. 나는 5 3 으로 정했다. 그리고 5 1 일때, 5 2 일 때를 먼저 생각해 보았다. 우선 순서대로 입력이 주어졌다면 아래와 같을 것이다.

 

입력: 5 1

경우의 수: (5) -> 1개

출력: 1

 

입력: 5 2

경우의 수: (0 + 5), (1 + 4), (2 + 3), (3 + 2), (4 + 1), (5 + 0) -> 6개

출력: 6

 

다음이 문제였다. 여기서 시간이 오래 걸렸는데, 다음과 같이 해결했다.

 

입력: 5 3

경우의 수: (0 + 5), (1 + 4), (2 + 3), (3 + 2), (4 + 1), (5 + 0)

즉, 5 2 로 입력이 주어질 때와 같은 꼴로 만들었다. 하지만 다른 점이 있다면, 입력이 5 2 일 때, 경우의 수 (0 + 5)는 0이 한 개로 만들었으니 5를 한 개로 만들 수 있는 경우의 수인 1이 필요했고, (1 + 4)에서는 1을 한 개로 만들었으니 4를 한 개로 만들 수 있는 경우의 수인 1을 더했다. 마찬가지로 1인 경우의 수가 총 6개 모여 5 2 의 출력 값이 6이 된 것이다.

 

하지만 5 3 으로 입력이 주어졌을 때는 경우의 수를 생각할 때 (0 + 5)는 0을 한 개로 만들었으니 5는 두 개로 만들 수 있는 경우의 수가 와야 한다. 마찬가지로 (1 + 4)의 경우 1이 한 개로 만들어졌다 생각하고 4를 두 개로 만들 수 있는 경우의 수를 필요로 했다...

 

따라서 간단하게 테이블로 만들면 다음과 같은 형태가 만들어진다. 너무 바로 테이블이 채워진 것 같지만 아래에 설명을 같이 보도록 하자.

 

table

	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	2	3	4	5	6
3	1	3	6	10	15	21

 

테이블을 보고 다시 설명하자면, 테이블 인덱스상 table(1, 2)에 해당하는 값은 1을 숫자 2개를 더해서 만드는 경우의 수이다. 이 경우 아래와 같은 의미를 갖는다.

 

(0을 1개의 숫자로 만드는 경우의 수)*(1을 1개의 숫자로 만드는 경우의 수)

+ (1을 1개의 숫자로 만드는 경우의 수)*(0을 1개의 숫자로 만드는 경우의 수)

 = table(0, 1)*table(1, 1) + table(1, 1)*table(1, 0)

 = table(1, 1) + table(1, 0)

 

 

table(2, 3) 은 값 2를 만들기 위해 3개의 숫자를 더해서 만드는 경우의 수를 의미하며 다음과 같이 나타낼 수 있다.

 

(0을 1개의 숫자로 만드는 경우의 수)*(2를 2개의 숫자로 만드는 경우의 수)

+ (1을 1개의 숫자로 만드는 경우의 수)*(1을 2개의 숫자로 만드는 경우의 수)

+ (2를 1개의 숫자로 만드는 경우의 수)*(0을 2개의 숫자로 만드는 경우의 수)

 = table(0, 1)*table(2, 2) + table(1, 1)*table(1, 2) + table(2, 1)*table(0, 2)

 = table(2, 2) + table(1, 2) + table(0, 2)

 

 

즉 어차피 앞에 더해지는 값은 1개를 이용한다고 생각했기 때문에 뒤에 더해지는 나머지의 경우만 찾으면 된다. 그 결과 table(n, k) = table(n, k-1) + table(n-1, k-1) + ... + table(0, k-1) 이라는 식이 나오게 된다. 게다가 여기서 table(n-1, k) = table(n-1, k-1) + ... + table(0, k-1) 이기 때문에, 처음의 식은 다음과 같이 나오게 된다.

 

table(n, k) = table(n, k-1) + table(n-1, k)

 

 

처음에는 위의 풀이처럼 하기 위해서 (N+1)x(K+1)의 크기의 배열을 생각했으나 마지막 점화식은 하나의 리스트로 충분히 구현이 가능하기 때문에 하나의 리스트로 해결을 했다.

import sys

N, K = map(int, sys.stdin.readline().split())
mod = 1000000000
table = [1]
table += [0] * N

for _ in range(1, K+1):
    for idx in range(1, N+1):
        table[idx] = (table[idx] + table[idx-1])%mod

sys.stdout.write(str(table[N]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다