[백준] 13302번 리조트

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

13302번: 리조트

 

문제

수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 즐기기 위해서는 하루로는 터무니없이 부족하다. 그래서 많은 이용객들은 3일 이상 연속으로 이용하기도 한다. KOI 리조트에서는 3일 연속 이용권을 할인된 가격 이만오천원에, 연속 5일권은 삼만칠천원에 판매하고 있다. 게다가 연속 3일권, 연속 5일권에는 쿠폰이 각각 1장, 2장이 함께 포함되어 있다. 쿠폰 3장은 하루 이용권 한 장으로 교환할 수 있다.

연속 3일권과 연속 5일권은 구입일로부터 연속으로 3일 혹은 5일간만 이용이 가능하지만 해당 기간을 모두 이용할 필요는 없다.

수영이는 N일의 여름방학 중 다른 일정으로 리조트에 갈 수 없는 날이 M일 있다. KOI 리조트를 사랑하는 수영이는 그 외의 모든 날을 KOI 리조트에서 보내고자 한다. 물론, 가장 저렴한 비용으로 리조트를 이용하고자 한다.

예를 들어, 여름방학이 13일이라고 하고, 여름방학 기간 중 리조트에 갈 수 없는 날이 4번째, 6번째, 7번째, 11번째, 12번째 날이라고 하자. 다음 표의 첫 번째 행은 13일의 여름방학을 나타내고, 리조트에 갈 수 없는 날은 검정색으로 표시되어 있다. 표의 두 번째 행과 세 번째 행은 수영이가 이용권을 구입하는 두 가지 방법을 나타낸다. 

두 번째 행의 구입 방법은 다음과 같다. 여름방학의 첫 번째 날에 연속 3일권을 구입하여 3번째 날까지 리조트를 이용하고, 구매시 1장의 쿠폰을 받는다. 5번째 날에는 하루 이용권을 구입하여 이용한다. 8번째 날에는 연속 3일권을 구입하여 10번째 날까지 리조트를 이용하고, 역시 구매시 쿠폰 1장을 받는다. 13번째 날에는 하루 이용권을 구입하여 리조트를 이용한다. 이렇게 하여 수영이가 리조트 이용을 위해 지불한 전체 비용은 70,000원이다. 

세 번째 행은 더 저렴한 비용으로 리조트를 이용하는 구입 방법이다. 여름방학의 첫 번째 날에 연속 5일권을 구입하여 5번째 날까지 리조트를 이용하고(4번째 날 제외), 구매시 2장의 쿠폰을 받는다. 그리고 8번째 날에 연속 3일권을 구입하여 10번째 날까지 리조트를 이용하고, 역시 구매시 쿠폰 1장을 받는다. 13번째 날에는 그때까지 받은 3장의 쿠폰을 하루 이용권 한 장으로 교환하여 리조트를 이용한다. 이렇게 하여 수영이가 리조트 이용을 위해 지불한 전체 비용은 62,000원이다.

여름방학 기간과 리조트에 갈 수 없는 날의 정보가 주어질 때, 리조트를 이용하기 위해서 수영이가 지불해야 하는 최소비용을 계산하는 프로그램을 작성하시오.

 

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수영이의 여름방학의 일수를 뜻하는 정수 N(1 ≤ N ≤ 100)과 수영이가 리조트에 갈 수 없는 날의 수 M (0 ≤ M ≤ N)이 순서대로 주어진다. M이 0인 경우 더 이상의 입력은 주어지지 않으며, M이 0보다 큰 경우 그 다음 줄에는 수영이가 리조트에 갈 수 없는 날이 1 이상 N 이하의 정수로 날짜 순서대로 M개 주어진다.

예를 들어, M이 3이고 입력의 두 번째 줄에 정수 “12 14 17”이 주어진다면 여름방학의 12번째, 14번째, 17번째 날에는 리조트에 갈 수 없음을 의미한다.

 

출력

표준 출력으로 주어진 입력에서 제시된 날들을 제외한 나머지 날 모두 리조트에 입장하기 위해서 지불해야 하는 비용의 최솟값을 출력한다.

 

 

 

풀이

N이 최대 100일이고 각 일별로 1일권, 3일권, 5일권을 구매하는 경우의 수를 다 계산하면
3^100으로 시간 내에 풀 수 없게된다. 그래서 문제를 DP를 이용하여 구현하였는데 Bottom - up 방식을 사용하였다.

Bottom-up은 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다.

 

dp = [[float("INF") for _ in range(110)] for _ in range(110)]           #day coupon
dp[0][0] = 0

dp의 각 상황을 구분짓기 위한 인자로 Day와 Coupon을 사용하였다.
dp[day(N)][coupon(M)]이면 N번째 날에 M개의 쿠폰을 가지고 있는 경우이다.
크기를 110까지 만든 이유는 bottom - up으로 100일째에 5일권을 사용한 경우에 105일까지 체크하기 때문에
여유있게 110까지 생성하였다.

 

for i in range(N+1):
    for j in range(40):
        if dp[i][j] == float("INF"):
            continue

모든 날에 대하여 체크하기 때문에 i는 N+1까지 조사해야한다. 
쿠폰은 100일동안 5일권만 구매하여 사용한다고 가정했을 때,
20*2로 최대 40개의 쿠폰만 생기기 때문에 j는 40까지만 체크해도 문제가 없다.

 

result = dp[i][j]

        if i+1 in holidays:
            dp[i+1][j] = min(result, dp[i + 1][j])

이제 dp 배열을 채워야한다.
holiday에 포함되는 경우에는 금액도 쿠폰 갯수도 변경되지 않기 때문에 날짜만 증가시키면 된다.

 

        if j >= 3 :
            dp[i + 1][j-3] = min(dp[i + 1][j - 3], result)

j가 3보다 큰 경우는 쿠폰이 3개 이상 있는 경우이기 때문에 금액 증가없이 1일을 이용할 수 있다.
날짜는 1 증가시키고 쿠폰의 갯수는 3개를 감소 시키면 된다.

 

        dp[i + 1][j] = min(result + 10000, dp[i + 1][j])

1일권을 구매하는 경우는 쿠폰의 갯수는 증가하지 않고 가격 + 10000원, 날짜 i가 1증가한다.

 

        for k in range(1, 4):
            dp[i + k][j + 1] = min(result + 25000, dp[i + k][j + 1])

3일권을 구매하는 경우에는 구매한 날로부터 3일간 (i가 3 증가하는 동안)
쿠폰의 갯수를 1개 증가시키고(j + 1) 가격은 +25000을 한다.

 

        for k in range(1, 6):
            dp[i + k][j + 2] = min(result + 37000, dp[i + k][j + 2])

5일권을 구매하는 경우 구매한 날로부터 5일간 (i가 5 증가하는 동안)
쿠폰의 갯수를 2개 증가시키고(j + 2) 가격은 +37000을 한다.

항상 dp의 값을 min을 이용하여 갱신하는 이유는 
0일차를 실행할 때 1일 차에 대하여
1일권을 구매한 경우 1일차 쿠폰 0개 
3일권을 구매한 경우 1일차 쿠폰 1개, 2일차 쿠폰 1개, 3일차 쿠폰 1개
5일권을 구매한 경우 1일차 쿠폰 2개, .... , 5일차 쿠폰 2개

이 때 1일권을 구매한 뒤 3일권을 구매하게 되면 2일차 쿠폰 1개가 된다.
처음부터 3일권을 구매하여 쿠폰이 1개인 경우(result)와 1일권, 3일권을 구매하여 2일차에 쿠폰이 1개인 경우(for문을 통하여 min함수로 비교되는 값) 중에서 더 싼 가격이 되는 상황을 고려해야하기 때문에 항상 현재 값(result)와 새로 생성되는 값(for) 중 작은값을 선택해야한다.

 

print(min(dp[N]))

결과는 N으로 입력받은 날 중 쿠폰 갯수와 상관없이 최소값을 선택하면 된다.

 

 

 

전체 코드

import sys

N, K = map(int, sys.stdin.readline().split())
if K == 0:
    holidays = ()
else:
    holidays = set(map(int, sys.stdin.readline().split()))
coupon = 0
dp = [[float("INF") for _ in range(110)] for _ in range(110)]           #day coupon
dp[0][0] = 0

for i in range(N+1):
    for j in range(40):
        if dp[i][j] == float("INF"):
            continue

        result = dp[i][j]

	#리조트에 가지 못하는 경우
        if i+1 in holidays:
            dp[i+1][j] = min(result, dp[i + 1][j])
        #쿠폰이 3개 이상 있는 경우
        if j >= 3 :
            dp[i + 1][j-3] = min(dp[i + 1][j - 3], result)
        #1일권을 구매하는 경우
        dp[i + 1][j] = min(result + 10000, dp[i + 1][j])
        #3일권을 구매하는 경우
        for k in range(1, 4):
            dp[i + k][j + 1] = min(result + 25000, dp[i + k][j + 1])
        #5일권을 구매하는 경우
        for k in range(1, 6):
            dp[i + k][j + 2] = min(result + 37000, dp[i + k][j + 2])

print(min(dp[N]))

로직을 이해하는 것이 조금 어렵지만 하나하나 따라가면 무리없이 이해할 수 있다고 생각한다.