백준 2225번 합분해 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 2225 합분해

2225 합분해

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

2225번: 합분해

문제 이해는 오래 걸리지 않았다. 예를 들면 인풋이 20 2 일 때 1+19, 2+18... 같은 경우의 수의 개수를 구해야 한다. 

 

알고리즘 분류

• 다이내믹 프로그래밍
• 수학

---

소스코드

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0] * 201 for _ in range(201)]

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

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

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

 

---

풀이

문제는 쉽게 이해했지만 어떤 방식으로 점화식을 도출해야 하는지 시간이 조금 걸렸고 다른 분들의 풀이도 참고했다. 

우선 N과 K의 관계에 대해서 알아야 한다. N = 1일 때 K를 경우의 수로 가진다. K=2 -> [0+1, 1+0], K=3 -> [0+0+1, 0+1+0, 1+0+0]... 문제에서 제한이 N, K ≤ 200 이므로 dp의 크기를 0부터 200까지로 설정하였다.

코드에서는 dp[n][k]는 n은 N을 k는 K를 의미한다.

이제 작은 수부터 경우의 수들을 확인해보면 아래의 표가 만들어진다. 표를 통해 위의 행과 왼쪽 행을 더하면 목푯값 i를 계산할 수 있다는 점을 알 수 있다.  

K ＼ N	1	2	3	4
1	1	1	1	1
2	2	3	4	5
3	3	6	10	15

이를 통해 점화식을 작성하면 dp[n][k] =dp[n][k-1] + dp[n-1][k]의 식이 성립된다.

이제 코드로 구현하기 위해 n=1일 때 dp를 채워주고 k=1일 때는 모두 1이므로 각 dp 채우기 전에 1로 저장해준다.

두 개의 for문으로 2부터 201까지 i와 j값을 활용하여 dp를 채우고 마지막에는 목표로 하는 값 dp[n][k]를 출력해주면 된다. 여기서 1,000,000,000으로 나누는 것을 까먹지 말자.

 

---

풀이 결과

2225 풀이 결과