99클럽 코테 스터디 _ 24일차 TIL (동적 계획법)

 

< 문제 >

[백준] 2225. 합분해 / 골드5

---

< 풀이 >

Dynamic Programming
시간복잡도 : O(NK)

 

def f():
    N, K = map(int, input().split())
    dp = [[0] * (N + 1) for _ in range(K + 1)]
    dp[0][0] = 1

    # DP 계산
    for k in range(1, K + 1):
        dp[k][0] = 1
        for n in range(1, N + 1):
            dp[k][n] = (dp[k][n-1] + dp[k-1][n]) % 1000000000

    print(dp[K][N])

f()

 

 

풀이 방식

1. dp 배열을 (K+1) X (N+1) 크기로 초기화한다.
   • dp[k][n]  :  k 개의 수를 사용하여 n 를 만드는 경우의 수
     • dp[2][3]은 "2개의 숫자를 사용해 3을 만드는 방법의 수"를 의미
   • dp[0][0]은 0개의 숫자를 사용해 0을 만드는 경우이므로 1이 됨.
2. dp 점화식
   • dp[i][j] = ∑ dp[i-1][j-x]  (x는 0~j의 값을 갖는다.)       * x는 숫자 j를 만들기 위한 마지막 숫자이다.
     • dp[i][j] =  dp[i-1][j-0] + dp[i-1][j-1] + ... + dp[i-1][j-x]
     • 마지막 숫자가 x일 때, 나머지 j-x를 i-1개의 숫자로 만드는 경우의 수를 더한 것
     • 계산한 값을 1,000,000,000을 나눈 나머지 값으로 dp[i][j]를 갱신
   • 예시 ) n = 3, k = 2  (3을 2개의 숫자의 합으로 만드는 방법의 수를 구하는 것)

     • j →	0	1	2	3
       dp[1][j]	1	1	1	1
       dp[2][j]	1	2	3	4

     • dp[2][3] = dp[1][3] + dp[1][2] + dp[1][1] + dp[1][0] = 1 + 1 + 1 + 1 = 4
     • 4가지 : (0,3), (1,2), (2,1), (3,0)
3. 점화식으로 dp 테이블을 갱신한 후, dp[K][N]을 출력

---

< 회고 >

🤔 💭_

product를 사용하여 다음과 같이 코드를 구현할 수 있지만, 이 경우에는 시간 복잡도가 O(N^K)가 되어 시간 초과가 발생한다.

from itertools import product

def f():
    N, K = map(int, input().split())
    # all_cnt 설명
    ''' [i for i in range(0, N+1)]  :  0부터 N까지의 모든 수를 담은 리스트
     for p in product( ..., repeat=K)  :  앞선 리스트에서 중복을 포함하여 K개의 숫자를 뽑는 모든 경우의 수를 구한다.
     if sum(p) == N  :  뽑은 수의 합이 N인 경우 리스트에 1을 담는다. '''
    all_cnt = sum([1 for p in product([i for i in range(0, N+1)], repeat=K) if sum(p) == N]) % 1000000000
    print(all_cnt)

f()

 

코드를 짧고 쉽게 짤 수 있지만 비효율적이게 되므로 dp로 풀이해야 한다.

 

문제를 풀면서 dp를 활용할 수 있는 다양한 방법에 대해 공부하게 되는 것 같다.