[Python] BOJ 2225 - 합분해

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

2225번: 합분해

# 일단.. 노트나 종이에 손으로 하나하나 경우의 수를 세면서 따져본다. 

   (그러면서 규칙이 발견되길 기도한다.)

  보통 DP문제는 앞에서부터 하나하나 세거나, 뒤에서부터 하나하나 세다보면 규칙이 보이는 경우가 많다.

 

# dp[N][K]를 K개의 수로 N을 만드는 방법이라고 하자. dp[0][1] = 1, dp[1][1] = 1...  

   dp[N][1]은 1개의 수로 N을 만드는 방법이므로 무조건 1이다.

   또한, dp[0][K] 역시 K개의 수로 0을 만들어야 하므로 0만 더해야한다. -> dp[0][K]도 무조건 1이다.

 

# 이제, 앞에서 부터(0부터 N까지) 하나하나 직접 경우의 수를 구해보았다.

   예를 들어 dp[1][1]은 1이고, dp[1][2]는 (0+1), (1+0) -> 2이다.

   dp[1][3]은 (0 + 1 + 0), (1 + 0 + 0), (0 + 0 + 1) -> 3인데 이것은 dp[1][2] + dp[0][2]와 같다.

   또한, dp[2][3]은 이와 마찬가지로 dp[0][2] + dp[1][2] + dp[2][2]와 같다.

 

dp[N][K]	0	1	2	3	4
1	1	1	1	1	1
2	1	2	3	4	5
3	1	3	6	10	15

 

# 이렇게 구하다보니 dp[N][K] = dp[0][K-1] + dp[1][K-1] + ... + dp[N][K-1]이 나왔다.

   그런데, 이렇게 구하면 매번 dp[N][K]를 구할 때마다 N번의 연산이 필요해서 오래 걸린다.

   dp Table을 채우다보니 dp[N][K]를 dp[N-1][K] + dp[N][K-1]로도 나타낼 수 있다는 것을 발견했다.

   (나중에 보니, dp[N-1][K] = dp[0][K-1] + dp[1][K-1] + ... + dp[N-1][K-1]이어서 

      dp[N][K] = dp[N-1][K] + dp[N][K-1]이 성립된다는 것을 알았다.)

 

# 따라서 dp Table을 채우고 dp[-1][-1]을 10억으로 나눈 값을 print해주면 끝

 

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
dp = [[0] * (N+1) for _ in range(K+1)]

for i in range(1, K+1):
	dp[i][0] = 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]) % 1000000000

print(dp[-1][-1] % 1000000000)

(solved.ac 티어: 골드 5)

 

# 하나하나 구하다보면 답이 나오고, '더 최적화 할 수는 없을까' 하면서 다시 되돌아보다보면

   dp문제는 풀리는 것 같다.