[알고리즘/DP] 2225번 : 합분해 - python

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

2225번: 합분해

 

---

• 문제
• 소요시간: 1시간 25분

---

• 설계하기(접근방법) 

1. 입력받기

 

2. 구현하기

접근법으로 알아낸 것이 아닌

수열을 그려보며 알게 되었다.

 

n과 k 의 형태는

 

0이 없는 경우에는

k가 n 미만일 때는

파스칼의 삼각형 형태를 보인다

 

     

n = 5, k = 3일 때는

 

1 1 3 / 1 3 1 / 3 1 1

1 2 2/ 2 1 2/ 2 1 1

로 6개다

 

여기서 0이 추가된다면 어떻게 될까?

각 수열의 자리에 0 이 들어가는 경우를 생각하면

 

k = 1일 때에다가 0을 2개 추가한 수열

k = 2일 때에다가 0을 1개 추가한 수열

k = 3일 때는 0이 없다

 

0을 추가한 각 수열의 개수를 구하는 법은

각 자리에 0을 추가한 순열을 만드는 것이다

 

k = 1일 때 0이 2개라면

 

5 0 0

0 5 0

0 5 5

 

즉 총 자리수는 k개가 되고

그 중에 2개의 자리를 골라 0을 넣어주면 된다

이는 조합과 같다

즉 3C2의 케이스를 k = 1일 때의 경우에 곱하면 된다

 

k = 2일 때 0 이 1개라면

 

역시 총 자리수는 k개가 되고

그중에 자리 1개를 골라 0을 넣어주면

3 C 1의 케이스를  k = 2일 때 곱하면 된다

 

이 방법은 k 가 n일 때 까지만 점점 곱해주어야 하는 순열의 개수가 늘어나고

 

k가 n개 이상일 때는 더이상의 새로운 조합이 없기 때문에

ex) k = 7 n = 6 일 때 부터는 0의 개수만 늘어난다

 

k = 7 n = 1일 때

7 자리 중에서 0이 들어갈 자리 6개 고르기

7C6

 

k = 7 n = 2일 때

7자리 중에서 0이 들어갈 자리 5개 고르기

7C5 .....

 

n = 6일 때까지의 개수를 구한다

 

3. 출력하기

 

결과에 %를 해서 출력한다

---

• 코드(출력)

import math

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

dp = [[1], [1,1]]

for i in range(3, n + 1):
    lst = [1 for _ in range(i)]
    for j in range(1, i - 1):
        lst[j] = dp[i - 2][j -1] + dp[i - 2][j]
    dp.append(lst)

result = 0


for i in range(k):
    if i > n - 1:
        break
    else:
        result += math.comb(k ,i + 1) * dp[n-1][i] 

print(result% 1000000000)

---

• 얻어갈 부분

1. 점화식으로 접근하지는 못했지만, 순열에 0이 들어가는 조합을 찾아서 문제를 풀 수 있었다. 문제의 조건을 좀 더 꼼꼼하게 읽자