문제

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

이용권 종류 가격 쿠폰지급
하루 이용권 10,000원 없음
연속 3일권 25,000원 쿠폰 1장
연속 5일권 37,000원 쿠폰 2장

연속 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원이다.

설명

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

www.acmicpc.net/problem/13302

  • 입력

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

최종 코드

으악 너무 이해하기 어려운 dp 문제였다.

우선 2차원 dp 배열을 dp[d:날짜][c:쿠폰개수] = min:최소비용으로 둔다. d번째 날에 c개의 쿠폰을 가지고 있을 때 들어가는 최소비용이 min이라는 뜻이다.

그리고 dp는 아래의 조건에 따라 순서대로 update한다.

  1. 리조트에 갈 수 없는 날인 경우 dp[d + 1][c] = min(dp[d + 1][c], dp[d][c])
  2. 하루이용권을 이용하는 경우 dp[d + 1][c] = min(dp[d + 1][c], dp[d][c] + 10000)
  3. 연속 3일권을 이용하는 경우 dp[d + 3][c + 1] = min(dp[d + 3][c + 1], dp[d][c] + 25000)
  4. 연속 5일권을 이용하는 경우 dp[d + 5][c + 2] = min(dp[d + 5][c + 2], dp[d][c] + 37000)
  5. 쿠폰이 3장 이상 있는 경우 하루이용권으로 교환 가능 dp[d + 1][c - 3] = min(dp[d + 1][c - 3], dp[d][c])

이렇게 글로만 보니까 도저히 이해가 안 돼서, 디버깅을 하면서 dp 배열을 엑셀로 채워보았다.

엑셀사진

13 5
4 6 7 11 12

위와 같은 입력이 들어온 경우, dp 배열은 사진과 같이 채워지게 된다. 빈 곳을 max 값이다. 최종 결과는 dp[13]에서의 최솟값인 62000원이 된다.

import sys

n, m = map(int, sys.stdin.readline().split())
days = [True] * (n + 1)
for x in list(map(int, sys.stdin.readline().split())):
    days[x] = False
dp = [[sys.maxsize] * 40 for _ in range(105)]
dp[0][0] = 0

for i in range(n):
    for j in range(37):
        if days[i + 1] == False:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 10000)
        dp[i + 3][j + 1] = min(dp[i + 3][j + 1], dp[i][j] + 25000)
        dp[i + 5][j + 2] = min(dp[i + 5][j + 2], dp[i][j] + 37000)

    for j in range(39, 2, -1):
        dp[i + 1][j - 3] = min(dp[i + 1][j - 3], dp[i][j])

print(min(dp[n]))

Enhanced

내용은 거의 비슷하지만 이중 for loop을 대신해서 dfs로도 이 문제를 풀 수 있다. 이 코드가 더 간단해보이는데 반해 아직 너무 익숙하지 않은 방식이라 Enhanced에 넣어 보았다. 언제쯤 이런 풀이를 한 번에 떠올릴 수 있을까?

import sys

def dfs(day, coupon):
    if day > n:
        return 0
    elif dp[day][coupon] != -1:
        return dp[day][coupon]

    if days[day] == False:
        dp[day][coupon] = dfs(day + 1, coupon)
    else:
        dp[day][coupon] = sys.maxsize
        dp[day][coupon] = min(dp[day][coupon], dfs(day + 1, coupon) + 10000)
        dp[day][coupon] = min(dp[day][coupon], dfs(day + 3, coupon + 1) + 25000)
        dp[day][coupon] = min(dp[day][coupon], dfs(day + 5, coupon + 2) + 37000)

        if coupon >= 3:
            dp[day][coupon] = min(dp[day][coupon], dfs(day + 1, coupon - 3))

    return dp[day][coupon]

n, m = map(int, sys.stdin.readline().split())
days = [True] * (n + 1)
for x in list(map(int, sys.stdin.readline().split())):
    days[x] = False
dp = [[-1] * 101 for _ in range(101)]

print(dfs(1, 0))

참고 사이트