[python] 백준 - 2225. 합분해

🤔문제 해결

G5 | dp, 조합론

DP는 역시 손으로 해야 제맛이다.

예시의 20, 2는 너무 크기 때문에 6, 4로 바꿔서 구해봤다.

열은 N 행은 K이다.

즉 2열 3행은 2를 숫자 3개로 만드는 방법의 가짓수다.

딱 보면 규칙이 보일 것이다. i, j 는 i-1,j 와 i,j-1의 합이라는 것을...

 

원래의 규칙은 경우의 수를 모두 직접 구해보면 3열4행을 구할 때는 3행의 0~4열까지의 숫자를 더한 값이다.

그 이유는

• 0을 숫자 2개로: (0,0)
• 1을 숫자 2개로: (0,1), (1,0)
• 2를 숫자 2개로: (0,2), (1,1), (2,0)

각각의 경우의 수 뒤에 2, 1, 0 을 붙여주면 숫자 2를 3개로 구성하는 경우의 수는 6이 나온다.

 

💨

💻소스 코드

N, K = map(int, input().split())

dp = [[0] * (N + 1) for _ in range(K + 1)]

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

    for row in dp:
        print(row)
    print()
print(dp[-1][-1])

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

2225번: 합분해

---

문제

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

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.