[백준] 2225번 합분해

💡문제접근

• 각각의 예시를 통해서 나올 수 있는 경우의 수를 구한 다음 표를 통해서 규칙성을 확인한 다음 점화식을 세워 해결할 수 있었다.
• 2차원 배열을 통한 다이나믹 프로그래밍 해결 방법도 익숙해지도록 많이 활용해봐야겠다.

dp배열	k=0	k=1	k=2	k=3	k=4	k=5	k=6	k=7	k=8	k=9	k=10	k=11	k=12
n=0	0	0	0	0	0	0	0	0	0	0	0	0	0
n=1	0	1	1	1	1	1	1	1	1	1	1	1	1
n=2	0	2	3	4	5	6	7	8	9	10	11	12	13
n=3	0	3	6	10	15	21	28	36	45	55	66	78	91
n=4	0	4	10	20	35	56	84	120	165	220	288	366	457

• 0 ~ N까지의 숫자 중에서 K개를 택해서 합이 N이 되도록 만들 수 있는 조합의 개수를 표로 나타낸 것이다.
• 예를 들어, dp[2][2] = (dp[2][1] + dp[1][2]) % 1,000,000,000이 된다는 것을 알 수 있다.

💡코드(메모리 : 32276KB, 시간 : 60ms)

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split())
dp = [[0] * 201 for _ in range(201)]

for i in range(1, 201):
    dp[1][i] = 1
    dp[2][i] = i + 1

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

💡소요시간 : 17m