13707번: 합분해 2
첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다.
www.acmicpc.net
문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
코드
n, k = map(int, input().split())
dp = [[0]*(k+1) for _ in range(n+1)] # j개의 수로 i를 만드는 방법의 수
for i in range(n+1):
dp[i][1] = 1 # 1개의 수로 i를 만드는 방법은 1개
for j in range(1, k+1):
dp[0][j] = 1 # j개의 수로 0을 만드는 방법은 1개
for i in range(1, n+1):
for j in range(2, k+1):
dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % 1_000_000_000
print(dp[n][k])
dp[i][j]에는 j개의 수로 숫자 i를 만드는 방법의 수를 저장한다.
1개의 수로 숫자 i를 만드는 방법은 i 본인 1개로 만드는 방법 1개뿐이다. 그리고 j개의 수로 0을 만드는 방법도 0을 j개 사용하는 방법 1개뿐이다. 이렇게 초기화를 해주고 반복문으로 dp 배열을 채워준다.
i-1을 j개의 수로 만드는 방법에서 1을 그 수들 중 하나에 더해주거나 i를 j-1개로 만드는 방법에 0을 1개 추가해서 숫자 i를 만들 수 있다. 따라서 점화식은 아래와 같다.$$dp[i][j] = dp[i-1][j]+dp[i][j-1]$$
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 20542번 받아쓰기 (0) | 2023.09.26 |
---|---|
[Python/파이썬] 백준 4811번 알약 (0) | 2023.09.13 |
[Python/파이썬] 백준 14226번 이모티콘 (0) | 2023.09.06 |
[Python/파이썬] 백준 17265번 나의 인생에는 수학과 함께 (0) | 2023.08.29 |
[Python/파이썬] 백준 11909번 배열 탈출 (0) | 2023.08.24 |