[SW 정글 21일차] 귀납적 사고(#DP #백준 9084 #백준 2294)

재귀에 대해서 공부하면서 '절차지향적 사고'가 아닌 '귀납적 사고'로 접근해야 한다는 얘길 들었다. 그 당시에 어렴풋이 이해했던 부분이 동적프로그래밍을 공부하면서 좀 더 선명히 이해가 되는 것 같아 기록해두고자 한다.

백준 9084

백준 9084

이 문제는 동전의 type이 주어질 때 주어진 금액을 만드는 모든 방법의 수를 출력하는 것이다. 동전의 최대, 최소 개수가 아닌 경우의 수를 모두 합한 값을 출력해야 한다.

주어진 금액에서 시작하여 모든 경우를 절차대로 타고 들어가면 복잡하다. 또한 '중복 부분 문제'가 발생한다. 그러므로 DP를 활용해본다.

1. 테이블 정의하기 dp[i] 는 'i를 만들기 위해 필요한 모든 방법의 수로 정의한다. 이렇게 정의해본 이유는 간단히 dp[주어진 금액] 하면 정답을 찾을 수 있기 때문이다. 2. 점화식 찾기 동전의 종류가 3종류라고 가정할 때 '3종류의 동전으로 i를 만들기 위해 필요한 방법의 수 = ①2종류의 동전(마지막 동전 금액 제외)으로 i를 만들기 위해 필요한 방법의 수 + ②3종류의 동전으로 (i-마지막 동전 금액)을 만들기 위해 필요한 방법의 수'로 표현할 수 있다. ①은 마지막 동전 금액을 제외 후 금액 i를 만들기 위한 경우의 수이다. 즉, 마지막 동전 없이 금액 i를 만들 수 있는 경우의 수이다. ②는 (i-마지막 동전 금액)을 만들기 위해 필요한 경우에 마지막 동전만 추가할 경우의 수를 나타낸다. 다시 말해 ①에서 마지막 동전이 포함되지 않을 경우의 수는 모두 구했으니 마지막 동전이 무조건 포함된 경우의 수를 ②에서 셀 수 있다. 예를들어 i = 6,금액 6을 동전 2, 3, 4로 만들 수 있는 모든 경우의 수를 구해보자. ①에서 2와 3을 이용해 6을 만드는 경우(2개) + ②는 2, 3으로 (6-4)를 구하는 경우(1개)로 총 3개임을 계산할 수 있다. ①, ②가 어떻게 계산되는지 절차대로 보는 것이 아니라 테이블을 정의한대로 결과를 뱉는다는 생각으로 넘어간다. 3. 점화식을 위한 초기 조건 dp 테이블을 0으로 초기화하고, dp index가 0일 때(= 0을 만들기 위한 경우의 수)를 1로 설정(경우의 수이기에 아무것도 선택 않는 경우가 존재함)한다.

 

t = int(input())

for _ in range(t):
    n = int(input())
    coin_types = list(map(int, input().split()))
    m = int(input())

    dp = [0] * (m+1)
    dp[0] = 1
    coin_types.sort()
    for coin in coin_types:
        for j in range(1, m+1):
            if j >= coin:
                dp[j] = dp[j] + dp[j-coin]

    print(dp[m])

 

재귀적으로 문제를 해결할 때도 어떤 함수 속의 함수 속으로 따라가면서 함수를 구상하지 않았다. 함수 속의 함수가 어떤 동작을 할 것이기에 믿고(?) 넘어가면서 함수를 구상하였다. DP의 점화식을 도출하는 것도 이와 유사하게 느껴졌다. DP 테이블 속으로 절차대로 따라가면서 생각하는 것이 아니라, DP 테이블로 정의한 값을 뱉을 것으로 믿고 넘어간다(귀납적으로).

백준  2294

이 문제는 앞 문제와 유사하다. DP를 활용하여 문제를 푼다. 다른 점은 dp를 업데이트 하는 부분이다. 업데이트 하는 부분만 살펴보면 다음과 같다.

...
for i in range(1, k+1):
    for coin in coin_type:
        if i >= coin:
            dp[i] = min(dp[i], dp[i-coin]+1)
        else:
            break
...

min 함수를 사용해서 dp[i]가 작은지, dp[i-coin] +1이 작은지 비교한다. 비교 대상이 dp[i]와 dp[i-coin]+1인데, dp[i]라고 하면 마지막 동전이 포함되지 않으면서 i를 만들 수 있는 최소의 개수이다. dp[i-coin]은 (i-coin)금액까지로 구한 최소의 개수이므로 마지막 동전을 추가하기만 하면 되기에 +1을 한다. 이 둘 중 작은 값으로 업데이트 하는 것이다. 앞서 문제의 ①, ②와 거의 동일한 구조임을 알 수 있다.

 

본 문제에서도 재귀와 유사하게, dp[i], dp[i-coin]은 각각 i와 i-coin을 만드는 최소의 개수를 반환한다고 믿고(!) (귀납적으로)코드를 짠다.

import sys
n, k = map(int, input().split())
coin_type = []

for _ in range(n):
    coin_type.append(int(input()))

coin_type = list(set(coin_type))
coin_type.sort()

dp = [54321] * (k+1)
dp[0] = 0

for i in range(1, k+1):
    for coin in coin_type:
        if i >= coin:
            dp[i] = min(dp[i], dp[i-coin]+1)
        else:
            break


if dp[k] != 54321:
    print(dp[k])
else:
    print(-1)