[Python] 13302 - 리조트 (골드4)

1. 문제 설명

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

13302번: 리조트

 

---

2. 아이디어

이렇게 경우의 수가 여러가지로 갈리면서 더 효율적인 케이스를 질문하는 문제는

대부분 dp를 활용해야 한다. 분명히 dp만으로 해결될 수 있는 문제..라고 지금은 생각하지만

예전의 나는 그렇지 않았나 보다.

괴랄하게 생겨먹은 bfs와 함께 문제를 풀었는데 그때 쓰인 아이디어가 아래와 같다.

(지금 다시 읽어보니까 DP조차 아님 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ)

아이디어를 리뷰해보자면 첫째날을 큐에 넣고 3일권, 5일권 각각의 경우에 대해서 이동시키고

그 분기점에서 또 각각 3일권, 5일권(휴일이 아니라면)을 소비한다.

그러다 쿠폰이 생기면 갯수만큼 row를 이동시킨다. 쿠폰이 3이상인 row에서의 분기점은

쿠폰을 쓰는 경우와 3일권, 5일권을 쓰는 경우까지 고려한다.

 

오랜만에 다시 보니까 그냥 노가다로 풀어버린 것 같기도 하고 ㅎㅎ

지금 생각해보면 아마 비슷한 로직으로 재귀함수만으로도 풀어버릴 수 있을만한 문제였다.

 

---

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(n, cache, schedule):
    queue = deque()
    queue.append([0, 0])
    cache[0][0] = 0
    
    while queue:
        day, coupon = queue.popleft()
        for voucher in range(1, 6, 2):
            tomorrow = day + voucher
            if tomorrow > n: # 범위를 벗어나는 경우 종료
                break

            if voucher == 1:
                if tomorrow in schedule: # 못 가는 날
                    if cache[day][coupon] < cache[tomorrow][coupon]:
                        cache[tomorrow][coupon] = cache[day][coupon]
                        queue.append([tomorrow, coupon])
                    continue
                if coupon >= 3: # 쿠폰을 쓰는 경우
                    if cache[day][coupon] < cache[tomorrow][coupon-3]:
                        cache[tomorrow][coupon-3] = cache[day][coupon]
                        queue.append([tomorrow, coupon-3])
                if cache[day][coupon] + 10000 < cache[tomorrow][coupon]: # 안 쓰는 경우
                    cache[tomorrow][coupon] = cache[day][coupon] + 10000
                    queue.append([tomorrow, coupon])
            if voucher == 3:
                if cache[day][coupon] + 25000 < cache[tomorrow][coupon+1]:
                    cache[tomorrow][coupon+1] = cache[day][coupon] + 25000
                    queue.append([tomorrow, coupon+1])
            if voucher == 5:
                if cache[day][coupon] + 37000 < cache[tomorrow][coupon+2]:
                    cache[tomorrow][coupon+2] = cache[day][coupon] + 37000
                    queue.append([tomorrow, coupon+2])
            

def solution():
    n, m = map(int, input().split())
    cache = [[2147483647]*41 for _ in range(n+1)]
    if m == 0:
        schedule = []
    else:
        schedule = list(map(int, input().split()))

    bfs(n, cache, schedule)
    print(min(cache[n]))

solution()