[Python] 백준 13302번: 리조트

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

13302번: 리조트

 

import sys
input = sys.stdin.readline
COST1, COST3, COST5 = 10000, 25000, 37000


def dfs(date, coupon):
    # Base case
    if date > N:
        return 0

    # Skip the function if dp already exists
    if dp[date][coupon] != -1:
        return dp[date][coupon]

    # Recursive case
    if date in unavailable_dates:
        dp[date][coupon] = dfs(date+1, coupon)
        return dp[date][coupon]

    dp[date][coupon] = min(dfs(date+1, coupon) + COST1,
                           dfs(date+3, coupon+1) + COST3, dfs(date+5, coupon+2) + COST5)
    if coupon >= 3:
        dp[date][coupon] = min(dp[date][coupon], dfs(date+1, coupon-3))

    return dp[date][coupon]


if __name__ == '__main__':
    N, M = map(int, input().split())
    unavailable_dates = []
    if M > 0:
        unavailable_dates = list(map(int, input().split()))

    dp = [[-1]*(46) for _ in range(106)]
    print(dfs(1, 0))

 

Top-down Dynamic Programming을 이용하였다.

 

우선, DP는 2차원이다. dp[DATE][COUPON]인데, 말그대로 각각 날짜와 쿠폰 갯수를 뜻한다.

 

이것을 기반으로 DFS 함수를 짜준다.

먼저 Base case는 date와 N을 비교하며, 조건에 걸리면 0을 리턴해준다.

그리고 dp의 값은 중간에 수정 없이, 최선의 값만을 넣도록 설계할 것이므로, dp가 초기 상태가 아니라면 해당 값을 리턴해준다.

다음으로 가장 중요한 일반적인 경우(Recursive case)이다. 그렇게 어렵지 않은데, 앞서 3가지의 경우(1일권, 3일권, 5일권)를 탐색한 뒤, 최소값을 dp에 넣어준다. 이후에, 만약 현재 쿠폰이 3개 이상이라면 이에 대한 경우까지 고려하여 dp의 값을 넣어준 뒤, 이를 리턴해준다.

 

전형적인 탑다운 형태의 DP 문제였다.

 

여담으로, 풀이에 대한 접근 방법은 이러했다. 먼저, 시간복잡도 고려하지 않고 비효율적인 DFS 함수를 짰고, 여기에 DP를 통해 불필요한 함수 호출을 줄여나가는 식이었다.

 

위는 탑다운, 아래는 바텀업 방식이다.