[백준 python] 2225번 합분해 - 동적프로그래밍(DP)

[백준 python] 2225번 합분해 - 동적프로그래밍(DP)

레벨: 골드 5

언어: python

---

문제풀러가기

2225번: 합분해

문제설명

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

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

입력값

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

출력값

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

📑풀이 과정

DP 동적프로그래밍은 문제를 보고 식을 만들 수 있으면 쉽게 풀 수 있다.

k가 1일 때는 N이 어떤 값이 오더라고 답은 1이다.

N 본인만 가능하기 때문이다.

 

k가 2일 때는 N+1로 구할 수 있다.

k가 2이고 N이 1이면 (1+0), (0+1) 로 2개

N이 2이면(2+0), (0+2), (1+1) 로 3개

이 처럼 N+1로 경우의 수가 늘어난다.

 

아래의 표처럼 수를 적다보면 규칙이 보일 것이다.

dp[2][2] = dp[1][2] + dp[2][1]

 

dp[K][N] = dp[K-1][N] + dp[K][N-1]

 

dp	N=       1	2	3	4	5
K=   1	1	1	1	1	1
2	2	3	4	5	6
3	3	6	10	15	21

위의 식을 만들었다면 코드로 작성하면된다.

대신

K=1 일 때는 1

k=2 일 때는 N+1

N=1 일 때는 k값을 dp배열에 넣어주어야 한다.

📋풀이 코드

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(1, N+1):
    if i == 1:
      dp[i][j] = 1
    elif i ==2:
      dp[i][j] = j+1
    elif j == 1:
      dp[i][j] = i
    else:
      dp[i][j] = dp[i-1][j] + dp[i][j-1]

print(dp[K][N] % 1000000000)

---