[G5] 백준 2225 - 합분해 (python3)

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

---

💡 해결방법

1차원에선 점화식이 보이지 않아서 2차원 grid에서 접근했다.

별다른 해결방법이 있던게 아니라 모든 경우의 수를 보고나면 규칙이 보일까 해서였다.

운이 좋게 해결할 수 있던 문제다.

 

아래는 dp table을 채우기 위해 완전탐색을 하는 코드다.

dp[n][k] = n을 k개의 합으로 구하는 방법

#2225 합분해 dp table 테스트
import sys
sys.setrecursionlimit(10**5)

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

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



def solution(n, k):
    # n, k = map(int, input().split())
    arr = [0]*k
    tmp = dict()

    def sol(arr, st_idx=0):

        if sum(arr) > n:
            return 0
        elif sum(arr) == n:
            st = ','.join(str(x) for x in arr)
            if st not in tmp:
                tmp[st] = True
                return 1
            else:
                return 0
        ret = 0
        for i in range(st_idx, k):
            for j in range(n,-1,-1):
                arr[i] = j
                ret += sol(arr, i+1)
            arr[i] = 0
        return ret

    return sol(arr)

for i in range(1, n+1):
    for j in range(1, k+1):
        dp[i][j] = solution(i,j)

for elem in dp:
    print(elem)

 

10 6을 입력하면

[0, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 3, 6, 10, 15, 21]
[0, 1, 4, 10, 20, 35, 56]
[0, 1, 3, 6, 10, 15, 21]
[0, 1, 4, 10, 20, 35, 56]
[0, 1, 5, 15, 35, 70, 126]
[0, 1, 6, 21, 56, 126, 252]
[0, 1, 7, 28, 84, 210, 462]
[0, 1, 8, 36, 120, 330, 792]
[0, 1, 9, 45, 165, 495, 1287]
[0, 1, 10, 55, 220, 715, 2002]
[0, 1, 11, 66, 286, 1001, 3003]

위 결과를 뱉는데, 규칙을 쉽게 확인할 수 있다.

 

dp[n][k] = dp[n-1][k] + dp[n][k-1]

---

🧾코드

#2225 합분해
n, k = map(int, input().split())
arr = [0]*k

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

for i in range(1, n+1):
    for j in range(1, k+1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000000000
for elem in dp:
    print(elem)
print(dp[n][k])