주어진 시간 안에 도착까지 갈 수 있는 최소의 스킵 수를 구하는 문제.
스킵을 하지 않으면 다음 도로는 대기 후 정시에 출발 가능하고 스킵을 하면 바로 출발할 수 있다.

Solution

처음에 짠 최소 스킵 횟수를 반환하는 단순한 4차원 DP로는 시간 초과... (idx, 스킵한 시간, 남은 시간, 스킵한 횟수),

살짝 비틀어서 생각해보면 dp[i][j]: i 인덱스까지 j번 스킵할 때 가능한 최소 거리 라고 정의하고 문제를 풀면 쉽게 풀린다.
소수점 계산이 까다롭기 때문에 소수점을 무시하기 위해 시간이 아닌 이동 거리를 사용하면 쉽다.

DP[i][j] = min( ceil( DP[i + 1][j] + dist[i]) , DP[i + 1][j - 1] + dist[i] )

일단 대략적인 모양은 이런 느낌이 되는데, ceil 함수에서 정시까지 기다리는 것을 처리하도록 하였다. 자세한 건 아래 코드 참고.

이제 for 문을 돌면서 0부터 n까지에 대해 i 번 스킵할 때 주어진 시간 안에 도착할 수 있는지 체크해주면 된다. 불가능하면 -1 리턴.

Source Code

from functools import lru_cache
from typing import List


class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:

        def ceil(d):
            return (d // speed if d % speed == 0 else d // speed + 1) * speed

        # idx 까지 num_skips 스킵을 써서 이동한 거리
        @lru_cache(maxsize=None)
        def solve(idx, num_skips):
            if num_skips < 0:
                return 987654321

            if idx >= len(dist):
                return 0

            # rest
            ret = ceil(solve(idx + 1, num_skips) + dist[idx])

            # skip
            ret = min(ret, solve(idx + 1, num_skips - 1) + dist[idx])

            return ret

        for i in range(len(dist)):
            ans = solve(0, i)
            if ceil(ans) <= hoursBefore * speed:
                return i

        return -1

1883. Minimum Skips to Arrive at Meeting On Time

Problem link

Problem Summary

Solution

Source Code