백준 2225 [합분해] 파이썬

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

2225번: 합분해

# 백준 2225
import math
N, K = map(int, input().split())
answer = math.comb(N+K-1, K-1)
print(answer%1000000000)

N+1 H K-1 이므로, 서로다른 N+1개의 자리 중 K-1 개를 중복하여 선택한다.

 

ex)  예를 들어 5를 2개로 나눈다고 했을때

    1+1+1+1+1=5 이고,

    1을 O로 치환하면

    O O O O O 가 된다.

   여기서 한 개의 벽을 설치한다고 하면,

    v O v O v O v O v O v  (v는 벽 설치 가능한 공간) 6개의 공간이 가능하다.

   따라서 6개의 공간에 1개의 벽을 설치하는 경우의 수와 같다. (벽을 설치하면 두 부분으로 나뉨) 

 

 

dp로도 풀 수 있다. (다른 분의 풀이를 올림)

https://jyeonnyang2.tistory.com/54

[Python] 백준 2225번: 합분해 풀이

n, k = map(int,input().split())
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(0, n+1):
    for j in range(1, k+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][k] % 1000000000)