문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
코드
n, k = map(int, input().split())
dp = [[0] * (n+1) for _ in range(k+1)] # 행은 사용한 정수 개수, 열은 만든 수
# 1개의 숫자로 N을 만드는 경우의 수는 1가지
for i in range(n+1):
dp[1][i] = 1
# 0을 n개의 숫자로 만드는 경우도 1가지
for i in range(k+1):
dp[i][0] = 1
if k > 1:
for i in range(1, k+1): # 사용한 정수 개수
for j in range(1, n+1): # 만든 수
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1_000_000_000
print(dp[k][n])
다이나믹 프로그래밍(Dynamic Programming)을 이용한 풀이이다.
dp 배열의 행은 사용한 정수의 개수 (1~ K), 열은 만든 수 (1~N)이다.
점화식은 다음과 같다.
dp[i][j] = (dp[i-1][j] + dp[i][j-1])
왜 이렇게 되냐면 0~N 사이의 K개의 정수로 N을 만들 수 있는 방법은 N-1을 K개의 정수로 만드는 경우에서 수 1개만 바꾸거나 N을 K-1개의 정수로 만드는 경우에서 0을 더하는 방법이 있기 때문이다.
이해하기 쉽게 예를 들자면, 3개의 정수로 4을 만드는 경우의 수를 구한다고 해보자.
그렇다면 우리는 (2개의 정수로 4을 만드는 경우의 수) + (3개의 정수로 3를 만드는 경우의 수)를 구하면 된다.
먼저 2개의 정수로 4를 만드는 경우의 수는 5가지이다.
(0, 4) (1, 3), (2, 2), (3, 1), (4,0)
여기서 0만 하나씩 추가하면 3개의 정수로 4를 만들 수 있다.
(0, 0, 4) (0, 1, 3), (0, 2, 2), (0, 3, 1), (0, 4, 0)
두번째로 3개의 정수로 3를 만드는 경우의 수는 10가지이다.
(0, 0, 3), (0, 1, 2), (0, 3, 0), (1, 0, 2), (1, 1, 1), ..., (3, 0, 0)
여기서 숫자 1개에만 1을 더해주면 3개의 정수로 4를 만들 수 있다.
(1, 0, 3), (1, 1, 2), (1, 3, 1), (2, 0, 2), (2, 1, 1), ..., (4, 0, 0)
그러므로 이 2개의 경우의 수를 더해주면 3개의 정수로 4을 만드는 경우의 수를 구할 수 있는 것이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 2624번 동전 바꿔주기 (0) | 2023.04.15 |
---|---|
[Python/파이썬] 백준 5557번 1학년 (0) | 2023.04.15 |
[Python/파이썬] 백준 9251번 LCS (0) | 2023.04.14 |
[Python/파이썬] 백준 12865번 평범한 배낭 (0) | 2023.04.13 |
[Python/파이썬] 백준 9084번 동전 (0) | 2023.04.12 |