알고리즘 - Python / 백준 - 2225번 : 합분해

2225번: 합분해 (acmicpc.net)

2225번: 합분해

 

---

풀이

• 0 ~ N 까지의 정수를 K번 더해서 N을 만들고 , 수를 중복하여 사용하거나 자리가 다르면 다른 경우로 처리한다.
• 이때 , 만들 수 있는 모든 경우의 수를 출력하는 문제다.
• 처음 문제를 보자마자 직관적으로 든 생각은 중복 조합 스타일의 문제다 라는 생각이었다.
• 과거 고등학교 시절 확통문제에서 단골 문제였던 X+Y+Z = 4 를 만족하는 음이 아닌 X, Y, Z 순서쌍의 개수는? 문제와 매우 흡사하다고 생각했다.
• 생각한 대로 중복 조합으로 문제를 풀고 정답이 나왔다.
• 골드 5 문제에서 중복조합은 너무 쉬운 풀이라고 생각해서 중간에 풀다가 DP 문제가 아닌가 싶어서 방향을 틀까도 하였다.
• DP로 풀까? 하는 아이디어가 떠오른 것은 부문제가 전체 문제의 답에 도움이 되기 때문이다.
• 만약 6을 3개의 수로 만드는 경우 3개의 수들 중 하나는 0 ~ 6일 것이고 그럼 한자리를 소거한 상태로 생각하면 다음과 같을 것이다.
• 6을 만드는데 한자리를 I로 소거했다는 것은 6-I를 2개의 수로 만드는 문제로 바뀌었다는 거고 이렇고 본 문제가 작은 소문제 들로 분해된다.
• 그럼 가장 작은 부분의 소문제부터 풀어나가면 결국 본문제의 답이 나오게 될 것이다.

 

import sys
n,k = map(int,sys.stdin.readline().split(" "))

def combi(n,c):
    ans = 1; div = 1
    if c == 0:
        return 1
    for i in range(1,c+1):
        ans *= n
        div *= i
        n -= 1
    return int(ans//div)

real_ans = 0
for i in range(1,k+1):
    real_ans += (combi(n-1,i-1) * combi(k,k-i))
print(real_ans% 1000000000)

---