DP 정복 - 4.2 다이내믹 프로그래밍을 사용한 문제 해결 : 예제 풀기 2

이번 예제는 '특정 점수에 도달하는 경우의 수 구하기' 다.

 

만약 3, 5, 10점을 얻을 수 있는 게임이 있을 때, 주어진 n 값에 도달할 수 있는 전체 경우의 수를 구하는 것이다.

예를 들어 n이 13일 때, (3, 10), (3, 5, 5), (5, 3, 5), (5, 5, 3), (10, 3)의 5가지 경우가 있다.

 

책에서 제시하는 점화식은 다음과 같다.

n에 도달하는 경우의 수 = (n-10)점에 도달하는 경우의 수 + (n-5)점에 도달하는 경우의 수 + (n-3)점에 도달하는 경우의 수

종료 조건

1. n < 0 일 때 0

2. n == 0 일 때 1

 

위의 두 가지 조건을 가지고 코드를 짜면 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)


def solve_recur(n):
    if n < 0:
        return 0
    if n == 0:
        return 1

    return solve_recur(n - 10) + solve_recur(n - 5) + solve_recur(n - 3)


def solve_dp(n):
    ar = [0 for _ in range(n + 1)]
    ar[0] = 1

    for i in range(1, n + 1):
        if i - 3 >= 0:
            ar[i] += ar[i - 3]
        if i - 5 >= 0:
            ar[i] += ar[i - 5]
        if i - 10 >= 0:
            ar[i] += ar[i - 10]

    return ar[n]


if __name__ == '__main__':
    n = int(input())
    print(solve_recur(n))
    print(solve_dp(n))

일단 책에 있는 거대로 짜긴 짰는데..

이걸 어떻게 끌어냈는지 잘 이해가 안 간다.

그래서 이전 절들에서 배웠던 지식으로 하나씩 따져보려 한다.

 

일단 재귀(recursion)로 풀려면 '동일 형태의 하위 문제로 나누기'에 대한 조건이 만족해야 한다.

n이 13일 때, 첫 번째 선택된 값을 3이라고 하면

n이 10일 때, 3과 5와 10을 가지고 10에 도달할 수 있는 답을 구하는 문제로 바꿀 수 있다.

n이 7일 때, 3과 5와 10을 가지고 7에 도달할 수 있는 답을 구하는 문제로,

n이 5일 때, 3과 5와 10을 가지고 5에 도달할 수 있는 답을 구하는 문제로,

n이 0일 때, 3과 5와 10을 가지고 0에 도달할 수 있는 답을 구하는 문제로 바꿀 수 있다.

(더 상세한 케이스는 지면상 생략)

 

위의 내용으로 미뤄보면 '동일 형태의 하위 문제로 나누기' 조건은 만족한다.

그렇다면 기본 경우에 대해 구해야 하는데

도달한 값이 음수면 버려야 하고, 0이면 카운트를 해주어야 한다.

따라서 상기의 n < 0인 경우와 n == 0인 경우에 대한 처리를 해주면 된다.

 

DP로 변환하는 부분의 경우는

ar [0] = 1이 핵심으로 보인다.

0점까지의 경우의 수는 아무것도 하지 않는 1가지이므로 해당 인덱스의 값을 1로 초기화 한 뒤에,

1부터 n까지 증분 해가면서 ar배열을 업데이트를 시켜주면 된다.

 

내가 100% 이해를 한 뒤 풀면 좋았겠지만

그래도 책의 내용들을 참고해서 사후 풀이를 해봤기에 의미가 있는 시간이었다.