[BOJ] Q2225 합분해

[BOJ] Q2225 합분해

Question

Language: Python

Difficulty: Gold 5

해당 문제는 점화식을 찾는 것이 핵심인 문제이다.

가령 n=6,k=4라고 했을때,

해당 경우는 의 합으로 표현할 수 있다. 0 + (6을 3가지 숫자의 합을 나타내는 경우의수) 1 + (5을 3가지 숫자의 합을 나타내는 경우의수) 2 + (4을 3가지 숫자의 합을 나타내는 경우의수) 3 + (3을 3가지 숫자의 합을 나타내는 경우의수) 4 + (2을 3가지 숫자의 합을 나타내는 경우의수) 5 + (1을 3가지 숫자의 합을 나타내는 경우의수) 6 + (0을 3가지 숫자의 합을 나타내는 경우의수)

이를 정규화 시켜보면 아래와 같다

F_n,k=F_0,k-1+F_1,k-1+F_2,k-1…+F_n,k-1 으로 표현할 수 있다.

또한 자세히 보면 F_n-1,k=F_0,k-1+F_1,k-1+F_2,k-1…+F_n-1,k-1

최종적으로 아래와 같은 점화식을 구할 수 있따. F_n,k=F_n-1,k+F_n,k-1

Solution 1

def solution():
    di=[[0]* (k+1) for _ in range(n+1)] 
    di[0][0]=1

    for i in range(k+1):
        di[0][i]=1   

    for i in range(1,n+1):
        for j in range(1,k+1):
            di[i][j]=di[i-1][j]+di[i][j-1]
    
    print(di[n][k]%1000000000)
if __name__ == "__main__":
    n,k=map(int,input().split())
    solution()  

해당 문제는 중복조합을 이용해서도 풀이를 할 수 있다. 주어진 n을 k개의 정수합을 나타내는 것이므로, n개의 물건을 통해 k개의 그룹으로 나누는 것으로 생각할 수 있다

즉, _n+1H_k-1을 통한 풀이도 가능하다.

Solution 2

from math import factorial
def solution():
    count=factorial(n+k-1)//(factorial(k-1)*factorial(n))
    print(count%1000000000)
    
if __name__ == "__main__":
    n,k=map(int,input().split())
    solution()