[Problem Solving] 백준 2225번 합분해 문제풀이

백준 2225번 문제풀이에 대해서 알아보겠다. 문제 해설은 다음의 링크를 확인하면 된다. 문제 해설

2225번: 합분해

해당 문제는 다이나믹 프로그래밍을 활용하여 해결해야 한다. 처음 문제 접근 과정에서 n = 20일 때를 먼저 생각해봐서 문제 풀이의 어려움이 있었다. 다이나믹 프로그래밍 문제를 해결할 때에는 처음부터 결과를 생각해보는 것이 좋다. 이 문제에서는 n = 1, k = 1일 때가 그 경우이다. 합분해 문제를 풀기 위해서는 다음 규칙에 대해서 알아야 한다.

 

• k = 1 일 때는 경우의 수가 1이다.
• n = 1 일때는 경우의 수가 k개다.

k = 1일 때는 경우의 수가 자기 자신으로 표현할 수 있기 때문에 경우의 수가 1이고, n = 1일 때는 1과 0을 이용하여 1의 위치만 바꿔주면 되므로 경우의 수가 k개가 된다.

 

위의 규칙을 적용하고, k = 3, n = 5일 때까지의 경우의 수를 표로 나타내면 다음과 같다. 표의 이름을 dp라 하겠다.

 

위의 표를 통해서 dp[3][2]을 구해보겠다.

 

1. dp[3][2] = dp[1][1] + dp[2][1] + dp[3][1]
2. dp[2][2] = dp[1][1] + dp[2][1]
3. dp[3][2] = dp[2][2] + dp[3][1]

위의 식을 통해 점화식을 구하면 다음과 같다.

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

앞서 설명한 2가지의 규칙과 위의 점화식을 적용하여 코드를 작성하면 다음과 같다.

 

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

data = [[0] * n for _ in range(k)]

for i in range(n):
    data[0][i] = 1

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