백준 문제 중 2225번, DP, ‘분해합’

백준 문제 중 2225번

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

문제

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

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

입력

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

출력

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

---

풀이

이번 문제의 핵심은 0을 신경 쓰는 것이다. 0이하의 숫자 중 0을 정수 1개로 만들수 있는 방법은 0 으로 존재하고 방법의 수는 1이다.

0 부터 6까지의 정수 중 4개로 6을 만드는 방법을 구하는 예시를 살펴보자

• 0개: [1, 0, 0, 0, 0, 0, 0],
• 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, 84]

각각 정수 0~N 그리고 개수 0~k의 방법의 수를 나타내는 배열을 dp[k][n]의 (k+1)*(n+1)크기의 배열이라 하자.

dp의 모든 성분을 0으로 초기화 하고 dp[0][0] = 1 자기자신을 하나의 수로 나타내는 방법은 자기자신 하나이므로 dp[1]의 모든항에 1을 초기값으로 넣어준다.

1. dp[2][0]은 0을 2개의 수로 나타내는법 즉 0+0이고, 이는 dp[1][0]의 방법 0에 +0을 해준것 과 같다.
2. dp[2][1]은 1을 2개의 수로 나타내는법 즉 1+0,0+1이고, dp[1][0]의 방법 0에 +1, dp[1][1]의 방법 1에 +0을 해준것 과 같다.
3. dp[2][2]은 2를 2개의 수로 나타내느법 즉 2+0, 1+1, 0+2 이고, dp[1][0] dp[1][1] dp[1][2]의 방법의 합과 같다.

이를 일반화 시키면 수도코드로 대략
dp[i][j] = sum(dp[i-1][:j+1]) 이 되고 이를 코드로 구현하면 아래와 같다.

%%timeit

from pprint import pprint

n,k = map(int,input().split())

 # 문제 출럭 및 오버플로우 방지용
M = 1000000000

 # 0으로 초기화 된 (k+1) x (n+1) 리스트 선언
dp = [[0 for _ in range(n+1)] for _ in range(k+1)]

 # 0이하의 정수중 0개로 0을 나타내는 법은 1개
dp[0][0] = 1

 # 자기자신을 1개의 수로 나타내는 법은 1개
for i in range(n+1): dp[1][i] = 1

 # dp[i]를 할당하는 코드
for i in range(2,k+1):
    for j in range(n+1):
        
         # n,k 은 각각 200이하의 정수이나 계속해서 sum을 하면 언젠가는
         # int의 최대크기인 2^31-1을 벗어나 임의정밀도를 다시 계산해야한다
         # 이를 방지하기 위해 sum연산마다 M으로 나눈 나머지를 취한다.
        dp[i][j] = sum(dp[i-1][:j+1])%M

pprint(dp)
print(dp[k][n]%M)

6 4
[[1, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5, 6, 7],
 [1, 3, 6, 10, 15, 21, 28],
 [1, 4, 10, 20, 35, 56, 84]]
84
6 4
[[1, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5, 6, 7],
 [1, 3, 6, 10, 15, 21, 28],
 [1, 4, 10, 20, 35, 56, 84]]
84
6 4
[[1, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5, 6, 7],
 [1, 3, 6, 10, 15, 21, 28],
 [1, 4, 10, 20, 35, 56, 84]]
84
6 4
[[1, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5, 6, 7],
 [1, 3, 6, 10, 15, 21, 28],
 [1, 4, 10, 20, 35, 56, 84]]
84
6 4
[[1, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5, 6, 7],
 [1, 3, 6, 10, 15, 21, 28],
 [1, 4, 10, 20, 35, 56, 84]]
84
6 4
[[1, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1],
 [1, 2, 3, 4, 5, 6, 7],
 [1, 3, 6, 10, 15, 21, 28],
 [1, 4, 10, 20, 35, 56, 84]]
84
1 loop, best of 5: 2.5 s per loop

배운점

%%timeit의 사용법을 알게 되었다.