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