[맛있는물회] [파이썬] <백준 알고리즘> 2225번 "합분해"

문제 조건

---

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

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

 

Input

---

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

 

Output

---

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

 

생각한 아이디어

---

맨첨에 product로 했다가 200까진것 보고 200^200?? 하면서 안되길래 바로 dp로 전환!

 

dp라는 힌트 얻고 쉽게 풀었다!

 

단순히 몇개 진행해보면 2차원 dp로 쉽게 풀이 가능한 문제

 

 K 1 2 3 4 ... k

N  1 2 3 4 

1  1 3 6 10

2  1 4 10 

3

...

n

dp[row][col]=dp[row][col-1]+dp[row-1][col] 

라는 점화식이 나오며 풀이 가능

 

소스코드

from itertools import product

if __name__ == "__main__":
   n,k=map(int,input().split())
   dp = [[0 for _ in range(k+1)]for _ in range(n+1)]
   for i in range(1,n+1):dp[i][1]=1
   for i in range(1,k+1):dp[1][i]=i

   for row in range(2,n+1):
      for col in range(2,k+1):
         dp[row][col]=dp[row][col-1]+dp[row-1][col]
   print(dp[n][k]%1000000000)

 

*파이썬 문법 정리