문제 개요
정렬된 숫자 리스트 days가 주어진다고 가정해 봅시다. 이 리스트는 버스를 반드시 타야 하는 날짜들을 의미합니다. 우리는 이 모든 날에 걸쳐 여행할 때 드는 최소 비용을 구해야 합니다.
버스 승차권은 다음 세 가지 종류가 있습니다.
- 1일권: 2달러
- 7일권: 7달러
- 30일권: 25달러
예를 들어 입력이 days = [1, 3, 5, 6, 28]이라면 출력은 9가 됩니다. 처음에 7일권을 구매하고, 29일째 되는 날 1일권을 하나 추가로 구매하면 총 9달러로 모든 여행 일정을 커버할 수 있기 때문입니다.
풀이 접근 방식: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)을 사용하면 효율적으로 해결할 수 있습니다. 각 날짜별로 최소 비용을 누적 계산하며, 세 가지 승차권 옵션 중 가장 저렴한 선택지를 찾아냅니다.
해결 과정은 다음과 같습니다.
- n := days 리스트의 최댓값
- days := days 리스트를 집합(set)으로 변환하여 빠른 조회 가능하게 함
- dp := 길이가 n+1인 0으로 초기화된 배열 생성
- i를 1부터 n까지 반복:
- i가 days 집합에 포함된 경우(여행하는 날):
- i >= 30이면: dp[i] := min(dp[i-1] + 2, dp[i-7] + 7, dp[i-30] + 25)
- 그렇지 않고 i >= 7이면: dp[i] := min(dp[i-1] + 2, dp[i-7] + 7, 25)
- 그 외의 경우: dp[i] := min(dp[i-1] + 2, 7)
- i가 days에 없으면(여행하지 않는 날): dp[i] := dp[i-1]
- i가 days 집합에 포함된 경우(여행하는 날):
- dp[n] 반환
핵심 아이디어는 특정 날짜 i에서 30일권을 산다면 그 권으로 i-30일부터 현재까지를 커버한다는 점입니다. 따라서 각 시점에서 직전 날짜들의 최소 비용에 새 승차권 가격을 더한 값들 중 최솟값을 선택하면 됩니다.
구현 예제
class Solution: def solve(self, days): n = max(days) days = set(days) dp = [0] * (n + 1) for i in range(1, n + 1): if i in days: if i >= 30: dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, dp[i - 30] + 25) elif i >= 7: dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, 25) else: dp[i] = min(dp[i - 1] + 2, 7) else: dp[i] = dp[i - 1] return dp[n] ob = Solution() days = [1, 3, 5, 6, 28] print(ob.solve(days))
입력
[1, 3, 5, 6, 28]
출력
9
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 마지막 여행 날짜입니다. 각 날짜마다 상수 번의 비교 연산만 수행하므로 매우 효율적입니다. 공간 복잡도 역시 DP 배열을 저장하기 위해 O(n)이 필요합니다.
days 집합 변환 덕분에 각 날짜가 여행일인지 확인하는 작업은 평균 O(1)의 시간에 처리되며, 전체 성능에 큰 부담을 주지 않습니다.