[Baekjoon] 2225. 합분해

🔗 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)!가 된다.