[백준/2225/파이썬] 합분해

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

2225번: 합분해

Problem

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
• 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

조건

• 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
• 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

SOL

0~N까지의 정수 K개를 더해서, 그 합이 N이 되는 경우의 수를 완전탐색으로 생각해본다고 하자.

 

완전탐색

• 재귀적으로 구현이 가능할 것 같다. 하지만, 재귀로 한다면, 계속 k개,k-1개 ...1개로 분해를 해야하므로, 함수의 calling이 엄청 많이 될거 같고, 결국 Time Limit에 걸릴거 같음!

DP

DP로는 간단하게 풀 수 있다.

• 20을 5개로 나눈 것은 [0+(20을 4개로 나눈것)] + [1+(19를 4개로 나눈것)] + ... + [19+(1을 4개로 나눈것)] + [20+(0을 4개로 나눈것)] 일 것이다. 즉, 나눈걸 또 나누고,또 나누고, Overlapping이 계속되고, 그 답으로 큰 답을 구할 수 있으므로, DP로 접근이 가능하다.

Bottom-up으로 풀기 위해서, DP table을 위의 성질에 맞게 정의해주면

• DP[K][N] = 정수 K개를 더해서, N이 되는 경우의 수.
• 예컨데, DP[3][0] 는 정수 3개를 더해서, 0이되는 경우의 수이다.

이 정의로 DP table을 그리면 아래와 같다.

DP[K][N] = DP[K-1][0] + DP[K-1][1] +....DP[K-1][N]

DP[K][N] = DP[K-1][N] + DP[K][N-1] 을 만족함! 

# 0 부터 N까지 정수 K개를 더해서, 그 합이 N이 되는 경우 

N,K=map(int,input().split())
DP=[[0]*(N+1) for _ in range(K+1)]

DP[1] =[1]*(N+1)

for i in range(1,K+1):
    DP[i][0] = 1
#print(DP)
for i in range(2,K+1):
    for j in range(1,N+1):
        DP[i][j] = (DP[i-1][j]+DP[i][j-1])%1000000000

print(DP[K][N])