코딩테스트/Python

[Baekjoon] 2225. 합분해

swwho 2025. 2. 18. 23:12
728x90
반응형

🔗 Problem Link

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


❔Thinking

  • 0부터 N까지의 숫자를 중복하여 K개 뽑아서, 합이 N이 되는 경우의 수를 반환한다.
  • 계산의 순서가 다르면 다른 경우로 생각한다. (ex - 1+2, 2+1은 다른 경우)

💻Solution

N, K = map(int, input().split())
a,b = 1,1

for i in range(1, K):
    a *= N + i
    b *= i

print((a // b) % 1000000000)

🗝️keypoint

  1. 합이 N이어야 하기 때문에, 공 N개를 K-1개의 칸막이로 구분짓는 경우와 같다고 생각할 수 있다.
  2. (n-1+r)! // (n-1)! * (r)!  인 중복 조합의 공식에 대입하면 (N+K-1)! // (N)! * (K-1)! 로 나타낼 수 있다. 여기서 N!을 분모와 분자에 각각 나누어주면, (N+1)! // (K-1)!가 된다.