2225 - 합분해

1) 문제 설명

특정 수를 몇개로 만들 수 있는지 구하는 것 

0도 허용되고, 중복이 허용되고, 여러번 사용도 가능 

 

예를 들어서, n = 1이고, k = 2이면 -> 1을 0,1만 써서 만드는 방법의 수를 구해야한다.

0+1, 1+0 => 2가지 

n=1이고, k=3이면, 3가지이다. n=1,k=2보다 1개가 더 늘어난다. 

0+0+1, 0+1+0, 1+0+0 

 

다른 경우를 따져보면,

n = 2, k = 2이면 2를 만드는데, 0,1,2를 사용하는 경우를 찾는것

0+2, 2+0, 1+1 -> 3가지

n = 2, k = 3이면, 총 6가지가 나온다.

0+0+2, 0+2+0, 2+0+0, 0+1+1, 1+0+1, 1+1+0

 

표로 그려보면 더 쉽게 점화식이 보인다

가로축이 n이고, 세로가 k이다. (n을 k개의 숫자로 만드는 방법

1가지로 1,2,3,4,...를 만드는 방법은 (0+1, 0+2, 0+3...밖에 없다)

1을 2가지 숫자로 만드는 방법은 (0+1, 1+0)으로 2가지

2를 2가지 숫자로 만다는 방법은 (0+2, 2+0, 1+1) 3가지

3을 2가지로 숫자로 만드는 방법은(0+3, 3+0, 2+1, 1+2) 4가지...

 

이제 1을 3가지 숫자로 만드는 방법은 (0+0+1, 0+1+0, 1+0+0) 3가지..

결국 가지수가 늘어나면 앞에 0을 하나씩 더 붙이는 꼴이기때문에 가지수만큼 늘어난다,

 

2를 3가지 숫자로 만드는 방법을 생각해보자 

0+0+2 -> 2를 3번 옮겨서 만들 수 있으므로 3가지

0+1+1 -> 0을 옮겨가면서 다른 숫자로 인식할 수 있으므로 3가지

총 6가지가 된다

 

3을 3가지 숫자로 만들어보자

0+0+3, 0+3+0, 3+0+0

0+1+2, 1+2+0, 2+0+1

0+2+1, 1+0+2, 2+1+0

1+1+1

총 10가지

 

이제 규칙이 보일것이다.

2보다 큰 수에서는 lst[i-1][j] + lst[i][j-1]으로 대각의 합이 다음 수이다

	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	2	3	4	5	6	7	8
3	3	6	10	15	21	28	36
4	4	10	20	35	56	84
5	5
6	6

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

lst = [ [0] * 201 for _ in range(201)]

for i in range(0, 201):
    lst[1][i] = 1
    
for i in range(0, 201):
    lst[i][1] = i

for i in range(2, 201):
    for j in range(2, 201):
        lst[i][j] = lst[i][j-1] + lst[i-1][j]
print(lst[k][n] % 1000000000)