[BOJ] 2225 - 합분해

문제

문제

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

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

입력

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

출력

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

예제 입력

20 2

예제 출력

21

문제 해결

기존 문제 해결은 2차원 dp 배열을 두고 k개로 만들수 있는 n을 dp[n][k]에 저장하면서 푸는 방법이 정석이다.
하지만 좀 더 간단하게(?) 1차원 배열로 풀어보자. n을 dp 배열로 설정한다.

0을 k개로 만들 수 있는 경우의 수는 1이다. 따라서 n이 0일때는 1을 저장한다. n == 0, dp[n] = 1

모든 수를 1개로 만들 수 있는 경우의 수는 1이다. 따라서 k가 1일때는 dp에 1을 저장한다. k == 1, dp[n] = 1

나머지 경우에는 조금 생각을 해보면 된다. 2개로 만들수 있는 3의 경우의 수를 가지고 생각해보자.
우선 1개일때는 전부 1이므로 dp 배열이 1로 초기화된다.
2개일때 0은 가지수가 1개이다. 따라서 dp[0] = 1이고 현재까지의 상황을 표로 나타내면 다음과 같다.

	0	1	2	3
1	1	1	1	1
2	1

k = 2, n = 1 일때 경우의 수는 k = 1 일때 n이 0인 경우와 1인 경우의 합이다. 왜냐하면 각각에 1과 0을 추가시켜 해당 경우의 수를 알아낼수 있다.

k = 2, n = 2 인경우도 똑같이 k = 1 일때의 n이 0, 1, 2인 경우의 합이다. 이때 k = 1 일때의 n = 0, n = 1 의 합은 dp[1] 에 저장되어 있으므로 dp[i] += dp[i-1] 의 점화식이 나온다.

	0	1	2	3
1	1	1	1	1
2	1	2	3	4

python 코드

n, k = map(int, input().split())
dp = [0] * (n+1)

for i in range(1, k+1):
  for j in range(0, n+1):
    if i == 1 or j == 0:
      dp[j] = 1
    else :
      dp[j] += dp[j-1]
  dp[j] %= 1000000000

print(dp[j])

느낀점

오랜만에 푸는 DP 문제여서 그런지 해결한뒤 너무 좋있다. 꾸준히 풀겠다.