[백준2225번] 합분해 / Python3

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

20 2

예제 출력 1

21

나의 풀이

잘 안풀려서 검색의 도움으로 풀 수 있었다. 우선 dp에 저장할 것을 정해보면 k개를 가지고 N을 만들 수 있는 개수이다. 이걸 정하고나서 점화식을 생각해보면 아래의 그림에서와 같이 k개를 가지고 N을 만드는 것을 (k-1)개에 a를 더한 것이 N이 되는 것으로 생각해 볼 수 있다.

위의 식을 이해했다면 아래의 점화식도 쉽게 이해가 갈 것이다. (k-1)개를 가지고 a를 0부터 N까지의 경우에 (N-a)를 만들 수 있는 개수를 구하는 것이다. 따라서 점화식은 아래와 같다.

점화식을 구했으니 코드로 옮기면 되는데 위의 점화식은 3중 for문을 사용하면 쉽게 구현할 수 있을 것이다.

그리고 처음 초기화를 해주어야할 부분은 k가 1인 경우이다. 1개로 모든 N에 대하여 만들 수 있는 개수는 1개씩인 것을 생각하고 dp[1] = [1,1,1,1,1,1,1...]과 같이 모두 1로 초기화를 해주어야한다. 그렇다고 k가 0일때에도 1이면 안된다는 것도 주의해햐한다.

• 참고 : https://mygumi.tistory.com/135

코드

# 2225번 합분해

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

dp = [[0 for _ in range(n+1)] for _ in range(k+1)]
dp[1] = [1 for _ in range(n+1)]

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