2225번 : 합분해 - Python

문제

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

풀이

정수 k개를 더해서 그 합이 n이 되는 경우

k=1인 경우
1가지 밖에 없다. 정수 n수 밖에 없다.

k=2인 경우
n+1가지 이다.
예를 들어 n=4라고 한다면
(0+4), (1+3), (2+2), (3+1), (4+0)이렇게 5개 이다.

k > 2인 경우
k-1인 경우의 0 ~ n까지의 합이다.
만약 n=4, k=3라면
(4를 2개로 나눈수) + (3을 2개로 나눈수) + (2를 2개로 나눈수) + (1을 2개로 나눈 수 ) + (0을 2개로 나누 수) 인 것이다.

코드

from sys import stdin, stdout

input = stdin.readline 

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

array = [i+1 for i in range(k+1)]


for i in range(2,k):
    array_n = [0 for i in range(k+1)]
    for j in range(k+1):
        array_n[j] = sum(array[0:j+1])
    array = array_n

if n==1:
    print('1')
else:
    print(array[-1]%1000000000)

다른 풀이

만약 n=4, k=3라면
(4를 2개로 나눈수) + (3을 2개로 나눈수) + (2를 2개로 나눈수) + (1을 2개로 나눈 수 ) + (0을 2개로 나누 수) 인 것이다.

이것을 점화식으로 표현하면
array[n][k] = array[0][k-1] + array[1][k-1] + ... + array[n]+[k-1]이다.

여기서
array[0][k-1] + array[1][k-1] + ... + array[n-1]+[k-1] = array[n-1][k] 임을 이용해서

array[n][k] = array[n-1][k] + array[n][k-1]으로 표현할 수 있다.

다른 코드

from sys import stdin, stdout

input = stdin.readline 

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

array = [[0]*(k+1) for i in range(n+1)]

array[0][0] = 1

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

print(array)

print(array[n][k] % 1000000000)