[코딩테스트] 합분해(2225)

합분해

DP

• ex.1) k = 2 이고, n = 1 이면 (0,1),(1,0) 2개

• ex.2) k = 4 이고, n = 1 이면 (0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0) 4개

• k = 1이면 n에 상관없이 n이 되는 경우의 수는 1개

• k = 2 일때, n =20이면

  • (10,10),
  • (0,20),(1,19),(2,18),(3,17),(4,16),(5,15),(6,14),(7,13),(8,12),(9,11)
    10개 * 2(반대로 뒤집은 상태)
    ==> 20 + 1 = 21개

import sys
input = sys.stdin.readline

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

for i in range(2,201):
	dp[i][1] = i
	for j in range(2,201):
		dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1_000_000_000
print(dp[k][n])

• 앞으로는 그려서 표로 확인하는 것도 고려해봐야겠다.