백준) 합분해 - python

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

 

 

이전의 동전 1

과 비슷한 문제이다.

 

우선 2개의 수로 6을 만드는 경우의 수는 어떻게 될까?

이를 생각하기에 앞서 정수 1개로 6을 만드는 경우를 생각해보자

 

 

당연하게도 0원부터 6원까지의 경우의 수는 모두 1개가 된다.

 

그럼 동전 2개로는 어떨까

3개 또한 다음과 같다.

 

 

규칙성이 보이기 시작하는 것이 정상이다.

 

이런 규칙성은 과연 합당할까?

 

좀 더 자세히 보자

단순 정수로만 표기하면 다음과 같이 규칙성을 찾을 수 없겠지만, 이를 이진법으로 바꾸면 간단하다.

 

 

단순히 이전 결과 값에 0 또는 1을 붙임으로써 해당 k 개로 정수 n을 만들 수 있는 경우의 수가 만들어진다

 

이를 코드로 변환하면 다음과 같다.

from itertools import combinations

n, k = map(int, input().split())

dp = [1] * (n + 1)


for i in range(2, k + 1):
    for j in range(1, n + 1):
        dp[j] = dp[j] + dp[j-1]


print(dp[n] % 1000000000)