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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

# dp[k][n] -> k개를 더해서 합이 n이 되는 경우의 수
# dp[k][n] = dp[k-1][n] + dp[k][n-1]
dp = [[0]*(N+1) for _ in range(K+1)]

# dp[x][0] = 1로 초기화
# dp[1][X] = 1로 초기화
for i in range(1, K+1):
    dp[i][0] = 1
for i in range(1, N+1):
    dp[1][i] = 1


for k in range(1, K+1):
    for n in range(1, N+1):
        if dp[k][n] == 1:
            continue  # skip
        dp[k][n] = (dp[k-1][n] + dp[k][n-1]) % 1000000000

print(dp[K][N])

---

🧂아이디어

DP

	0	1	2	3	4	5	6
1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7
3	1	3	6	10	15	21	28
4	1	4	10	20	35	56	64

• dp[k][n] -> 0~n까지의 정수 k개를 더해서 합이 n이 되는 경우의 수
• dp[k][n] = dp[k-1][n] + dp[k][n-1]

---

🧐

• 딱 보자마자 2차원 dp로 풀어야지라고 생각했던 문제
• dp[n][k]로 생각하면 점화식 떠올리기 좀 어렵고 dp[k][n]로 생각하니 간단하게 풀렸다