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

접근

• 우선 직접 경우의 수를 구하는 것을 통해 N과 K의 관계를 구해야한다.

가령 K=4의 경우의 수를 구하고 싶다면 N=0일 땐 0,0,0,0 1가지 N=1일 땐 1,0,0,0을 자리 바꾸어 4가지 N=2일 땐 2,0,0,0을 자리 바꾸어 4가지 + 1,1,0,0을 자리바꾸어 6가지 N=3일 땐 3,0,0,0 4가지 + 2,1,0,0 6가지 + 1,2,0,0 6가지 + 1,1,1,0 4가지

• 다음과 같은 계차수열의 규칙을 찾을 수 있다.

• K = 2일 때 N 값에 따른 답(경우의 수)

N	0	1	2	3	4	5	…
경우의 수	1	2	3	4	5	6
1차 증가량	-	1	1	1	1	1
2차 증가량	-	-	0	0	0	0

• K = 3일 때 N 값에 따른 답

N	0	1	2	3	4	5	…
경우의 수	1	3	6	10	15	21
1차 증가량	-	2	3	4	5	6
2차 증가량	-	-	1	1	1	1

• K = 4일 때 N 값에 따른 답

N	0	1	2	3	4	5	…
경우의 수	1	4	10	20	35	56
1차 증가량	-	3	6	10	15	21
2차 증가량	-	-	3	4	5	6

• 즉 K값에 따라 차원이 증가하는 계차수열임을 알 수 있다.

• 2중 for문을 통해 증가하는 계수를 구하는 테이블을 co를 만들면 다음과 같이 된다.

N	1	2	3	4	5	6	…
K=1	0	0	0	0	0	0
K=2	1	1	1	1	1	1
K=3	2	3	4	5	6	7
K=4	3	6	10	15	21	28
K=5	4	10	20	35	56	84

• co[i][j] = co[i-1][j] + co[i][j-1]임을 알 수 있다.

• 합이 N이 되는 경우의 수를 저장한 다이나믹 테이블dy를 만들고 순차적으로 구한다.

  • dy[i-1] + co[K-1][i-1]을 통해 dy[i]를구할 수 있다.

코드 구현

if __name__=="__main__":
    N, K = map(int,input().split())
    dy = [0] * (N+1)
    dy[0] = 1
    co = [[x for _ in range(N)] for x in range(K)]
    for i in range(1, K):
        for j in range(1, N):
            co[i][j] = co[i-1][j] + co[i][j-1]
    for k in range(1, N+1):
        dy[k] = dy[k-1] + co[K-1][k-1]
    print(dy[N]%1000000000)

• co 테이블을 만들고 보니 dy[N][K]는 co[N][K+1]과 동일하다는 사실을 알 수 있었다.
• 아래와 같이 코드를 작성해도 똑같이 정답이 된다.

if __name__=="__main__":
    N, K = map(int,input().split())
    dy = [0] * (N+1)
    dy[0] = 1
    co = [[x for _ in range(N)] for x in range(K+1)]
    for i in range(1, K+1):
        for j in range(1, N):
            co[i][j] = co[i-1][j] + co[i][j-1]
    print(co[K][N-1]%1000000000)

다른 접근

• 사실 이 문제는 중복 조합을 이용하여 풀 수 있다.

answer = _(n+1)H_(k-1) = _(n+k-1)C_(n)

• 의자가 N개 있을 때 K개 책상에 의자를 배치하는 경우의 수 (순서 고려 및 0개 허용)

  • n+1 : 0부터 N까지의 개수
  • K-1 : 공간을 K개로 나누는 칸막이의 수

코드

def factorial(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

def combination(n, r):
    numerator = factorial(n)
    denominater_1 = factorial(r)
    denominater_2 = factorial(n-r)
    return numerator // (denominater_1 * denominater_2)

if __name__=="__main__":
    N, K = map(int,input().split())
    answer = combination(N+K-1, N)
    print(answer%1000000000)

주의 사항

• 파이썬에서는 이 방법이 보다 효율적이다.
• 그러나 팩토리얼 연산의 경우 n, k에 따라 그 값이 기하급수적으로 커지므로 동적타이핑을 지원하지 않는 다른 언어에서는 overflow가 발생할 위험이 높다.
• 때문에 중복조합이 아닌, 2차원 리스트를 이용하는 것이 오히려 정석에 가깝다.