[BOJ 17981] - Bus Ticket (DP, Python)

보양쿠·2022년 10월 19일

DP boj

BOJ

목록 보기

52/252

1년 전에 풀다가 포기하고, 3달 전에 결국 풀어낸 꽤 어려운 DP 문제가 있다.
그 문제를 풀이해보겠다.

BOJ 17981 - Bus Ticket 링크
(2022.10.19 기준 G3)
(치팅하면 평생 버스 놓치고 택시 탔는데 뒤에 타도 되는 버스 따라옴)

문제

단일 여행 티켓 가격 s, 기간 여행 티켓 가격 p, 기간 여행 티켓 기간 m, 여행 횟수 n 그리고
i번째 여행 날짜가 n개 만큼 주어질 때, 여행하는데 드는 최소 비용

알고리즘

첫번째 여행부터 차례대로 티켓 가격과 기간 여행 티켓 기간에 따른 여행 비용을 알아나가야 한다. (Bottom-Up DP)

풀이

Bottom-Up DP는 일단 점화식을 세워야 한다.

j + 1 = i번째 여행 날짜까지 기간 여행 티켓이 커버 가능한 최소 여행 날짜라고 한다면
dp[i] = min(dp[i - 1] + s, dp[j] + p) 가 점화식이 된다.
i-1번째 여행 후 단일 티켓을 사서 i번째 여행을 하거나 j번째 여행 후 기간 티켓을 사서 i번째 여행까지 하거나 둘 중 하나이다.

j는 i - 1부터 1씩 감소하면서 여행 날짜 차이가 m보다 같거나 커질 때 break하면 j가 찾아진다.
# j + 1번째 여행 때 기간 티켓을 샀을 때 i번째 여행이 커버가 되는 최소 j
for j in range(i - 1, -1, -1):
	if ti[i] - ti[j] >= m:
    	break
그리고 만약 기간 티켓이 단일 티켓보다 싸다면, 무조건 기간 티켓을 사는 것이 싸다. 그러므로 이럴 경우엔 편의상 단일 티켓 가격에 기간 티켓 가격을 덮어씌우자.

주의사항

dp는 n+1 크기 만큼 만들어서 dp[1]부터 시작해야 한다.
이유는 다음과 같다.
만약 j를 찾을 때 모두 커버가 되어서 0까지 내려간다면, 그 의미는 기간 티켓 하나가 i번째 여행까지 커버가 가능하다는 뜻이다.
그러므로 기간 티켓 가격만 포함되어야 하므로 dp[0] = 0이 필요한 것이다.
~~(이렇게 안해도 모두 커버가 안되면 예외 케이스로 두어서 따로 처리하면 되겠지만.. 굳이..?)~~

코드

import sys; input = sys.stdin.readline

def solve():
    # 단일 여행 티켓 가격, 기간 여행 티켓 가격, 기간 여행 티켓 기간, 여행 횟수
    s, p, m, n = map(int, input().split())
    # i번째 여행 날짜
    ti = [0] + list(map(int, input().split()))

    # 만약 단일 티켓보다 기간 티켓이 싸다면 단일 티켓을 구매할 필요가 없으므로
    # 편의상 단일 티켓에 기간 티켓 가격을 저장하자.
    if s > p:
        s = p

    # 점화식
    # j + 1 = i번째 여행 날짜까지 기간 여행 티켓이 커버 가능한 최소 여행 날짜
    # dp[i] = min(dp[i - 1] + s, dp[j] + p) (j번째 여행 이후로 기간 티켓을 사므로)
    dp = [0] * (n + 1)
    dp[1] = s # 첫번째 여행은 단일 티켓 구매
    for i in range(2, n + 1):
        # j + 1번째 여행 때 기간 티켓을 샀을 때 i번째 여행이 커버가 되는
        # 최소 j롤 찾자.
        for j in range(i - 1, -1, -1):
            if ti[i] - ti[j] >= m:
                break
        dp[i] = min(dp[i - 1] + s, dp[j] + p)
    print(dp[-1])

solve()