합분해[백준 2225] - python

 

기본적인 다이나믹 프로그래밍이다.

배열을 그리고 초반 몇개를 직접 시도해보면 규칙이 보일거다

 

정답 코드 먼저 보자

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

dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(0, n+1) :
  for j in range(1, k+1) :
    dp[i][j] = dp[i-1][j] + dp[i][j-1]

print(dp[n][k] % 1000000000)

 

k = 1 인경우 모든 숫자는 1이다.

k = 2 인경우 모든 숫자는 (n+1)을 가진다.  n=2: (0,2)(1,1)(2,0)   n=3: (0,3)(1,2)(2,1)(3,0)   n=4: (0,4)(1,3)(2,2)(3,1)(4,0)

k= 3 인경우 모든 숫자는 k=2,n=n 일때와 k=3,n=n-1일때의 경우의수의 합이다. n=2: (0,0,2)(0,2,0)(2,0,0)(1,1,0)(1,0,1)(0,1,1)

---

k= i 인경우 모든 숫자는 k=i-1,n=n 일때와 k=i,n=n-1일때의 합이다 dp[i][j] = dp[i-1][j] + dp[i][j-1]

 

 

n = 1 인경우 k의 숫자와 같은 값을 가진다. k=2: (0,1)(1,0)   k=3: (0,0,1)(0,1,0)(1,0,0)  k=4: (0,0,0,1)(0,0,1,0)(0,1,0,0)(1,0,0,0)

 

n\k	0	1	2	3	4	5	6
0	1	1	1	1	1	1	1
1	0	1	2	3	4	5	6
2	0	1	3	6	10	15	21
3	0	1	4	10	20	35	56
4	0	1	5	15	35	70	126
5	0	1	6	21	56	126	252
6	0	1	7	28	84	210	462

 

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

2225번: 합분해