2225번 파이썬

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

2225번: 합분해

이 문제는 규칙을 찾고 dp를 이용해서 푸는 문제이다.

	n=1	n=2	n=3	n=4	n=
k=1	1	1	1	1	1
k=2	2	3	4	5	6
k=3	3	6	10	15	21

n=1일때는 k의 개수에 따라 경우의 수가 달라지고 k가 1일때는 경우의 수가 한개이므로 전부다 한개이다!

따라서 이 두경우는 모두 초기화를 해주어야한다. 또한, k=2일때도 경우의수가 n+1이므로 이 경우도 같이 초기화를 해준다.

그리고 k,n이 2이상부터 p[k][n]이 p[k-1][n]+p[k][n-1]이라는 것을 알 수 있는데 이건 쉽게 예제로 생각해보면 k,n이 3,3인 dp를 구할때 2,3과 3,2를 구하게 되는데

2,3의 경우 개수를 한개 증가시키면(0을 추가시켜주면됨) 3,3이 되고

(2,1),(1,2),(3,0),(0,3) 

3,2의 경우 숫자를 하나만 증가시켜주면 3,3이 된다.

(2,0,0), (0,2,0),(0,0,2),(1,1,0),(0,1,1),(1,0,1)

이 내용을 코드로 작성해보면 다음과 같이 작성할 수 있다!

import sys
input = sys.stdin.readline
n,k=map(int,input().split())
p = [[0 for _ in range(201)] for __ in range(201)]
for i in range(n+1):
  p[1][i]=1
  p[2][i]=i+1
for k_i in range(2,k+1):
  p[k_i][1]=k_i
  for n_i in range(2,n+1):
    p[k_i][n_i]=(p[k_i-1][n_i]+p[k_i][n_i-1])%1000000000

print(p[k][n])