[Python] 백준 13302번: 리조트

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

13302번: 리조트

1.  bfs+dp를 이용하여 접근하였다. 쿠폰은 최대 100 / 5 * 2 = 40개를 가질 수 있으므로 열을 40으로 잡았다.

2. 다음날이 가능하면 현재날+1, 현재 날 + 3일, 현재 날+ 5일로 각각 받을 수 있는 쿠폰의 개수 배열에 최솟값을 넣어준다.

3. 다음날이 불가능하면 다음날을 queue에 삽입하고 반복문을 탈출한다.(다음날이 불가능하면 티켓을 아에 살수가 없음)

 

INF = 2147000000
n, m = map(int, input().split())
imp = [0 for _ in range(n+1)]
dp = [[INF for _ in range(41)] for _ in range(n+1)]
for x in list(map(int, input().split())):
    imp[x] = 1
queue = deque()
queue.append([0, 0])
dp[0][0] = 0
while queue:
    day, coupon = queue.popleft()
    for i in range(1, 6, 2):
        next = day + i
        if next > n:
            continue
        if i == 1:
            if imp[next]:
                dp[next][coupon] = min(dp[next][coupon], dp[day][coupon])
                queue.append([next, coupon])
                break
            if coupon >= 3 and dp[next][coupon-3] > dp[day][coupon]:
                dp[next][coupon-3] = dp[day][coupon]
                queue.append([next, coupon-3])
            if dp[next][coupon] > dp[day][coupon] + 10000:
                dp[next][coupon] = dp[day][coupon] + 10000
                queue.append([next, coupon])
        if i == 3 and dp[next][coupon+1] > dp[day][coupon] + 25000:
            dp[next][coupon+1] = dp[day][coupon] + 25000
            queue.append([next, coupon+1])
        if i == 5 and dp[next][coupon+2] > dp[day][coupon] + 37000:
            dp[next][coupon+2] = dp[day][coupon] + 37000
            queue.append([next, coupon+2])

print(min(dp[n]))