[백준] 2252 합분해 (Python 파이썬)

www.acmicpc.net/problem/2225

2225번: 합분해

문제 설명

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

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우).

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

---

풀이 과정

이 문제는 코드는 간단해보일지 몰라도, 아이디어를 떠올리는 과정이 굉장히 까다로웠다.

나는 DP와 순열과조합의 개념을 조합하여 아이디어를 떠올렸다.

 

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 d[N][K]에 저장한다고 하자.

 

N = 2, K = 1 일 경우 0부터 2까지의 정수 1개를 더해 합이 2이 되는 경우의 수이므로,

만들 수 있는 경우의 수는 (2) 한가지 밖에 없을 것이다. 즉, d[2][1] = 1

 

N = 2, K = 2 일 경우 0부터 2까지의 정수 2개를 더해 합이 2이 되는 경우의 수이므로,

(2+0), (0+2), (1+1) 이렇게 세 가지가 존재한다. d[2][2] = 3

 

N = 2, K = 3 일 경우 0부터 2까지의 정수 3개를 더해 합이 2이 되는 경우의 수이므로,

(0+0+2), (0+2+0), (2+0+0), (0+1+1), (1+0+1), (1+1+0) 이렇게 여섯가지가 존재한다. d[2][3] = 6

 

그럼 이제 규칙을 한번 살펴보자.

K=2인 경우와 K=3인 경우를 비교해 보자.

 

K=3인 경우는 K=2인 경우에 정수 1개를 더 추가한 것이다. 합은 그대로인 상태로.

 

즉, 0부터 2까지의 정수 3개를 더해 합이 2이 되는 경우의 수는,

0부터 2까지의 정수 2개를 더해 합이 2-A이 되는 경우의 수에, 정수 A를 더 추가하여 나타내는 것이다.

 

식으로 나타내 보면, d[2][3] = d[2][2] + d[1][2] + d[0][2] 와 같이 나타낼 수 있다.

                                                        0추가       1추가      2추가

 

즉, d[n][k] = d[0][k-1] + d[1][k-1] + d[2][k-1] + ... d[n][k-1] 과 같이 나타낼 수 있다.

 

이를 코드로 나타내면 다음과 같다.

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

하지만, 이러한 형식으로 3중 for문을 돌게되면, 시간복잡도가 O(KN^2)이 된다.

즉 거의 O(N^3)에 수렴하게 된다.

 

그래서 다음과 같은 아이디어를 떠올릴 수 있다.

 

d[n][k] = d[0][k-1] + d[1][k-1] +  ...  + d[n-1][k-1] + d[n][k-1] 에서

d[n-1][k] = d[0][k-1] + d[1][k-1] + ... + d[n-1][k-1] 이므로, 파란부분을 치환하면

 

d[n][k] = d[n-1][k] + d[n][k-1] 과 같이 나타낼 수 있다.

 

코드로 나타내면 다음과 같다.

n, k = map(int, input().split())

d = [[0]*(k+1) for _ in range(n+1)]

for i in range(k+1):
    d[0][i] = 1

for i in range(1, n+1):
    for j in range(1, k+1):
        d[i][j] = d[i][j-1] + d[i-1][j]
        d[i][j] %= 1000000000

print(d[n][k])

d[0][i] 는 0을 나타낼 수 있는 경우의 수는 무조건 1가지 이기 때문에 1로 설정을 해주었다.

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !