Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 기차 티켓 최소 비용 구하기: 동적 계획법(DP) 완벽 가이드

기차 여행으로 유명한 나라가 있다고 가정해 보겠습니다. 우리는 1년 전부터 기차 여행 계획을 세워 왔으며, 올해 여행할 날짜들이 담긴 배열을 가지고 있습니다. 각 날짜는 1부터 365 사이의 정수로 표현됩니다.

기차표는 다음과 같은 세 가지 방식으로 판매됩니다.

  • 1일권: costs[0]달러
  • 7일권: costs[1]달러
  • 30일권: costs[2]달러

각 패스는 해당 일수만큼 연속적으로 여행할 수 있는 권리를 제공합니다. 예를 들어, 2일째에 7일권을 구매하면 2일부터 8일까지(2, 3, 4, 5, 6, 7, 8일) 쉬지 않고 여행할 수 있습니다.

우리가 풀어야 할 문제는 주어진 날짜 목록의 모든 날에 여행하기 위해 지출해야 하는 최소 금액을 구하는 것입니다.

예제 살펴보기

입력이 days = [1, 4, 6, 7, 8, 20]이고 costs = [2, 7, 15]라고 가정해 보겠습니다. 이때 최소 비용은 11입니다.

그 이유는 다음과 같습니다.

  • 1일: 1일권(costs[0] = $2)을 구매하여 1일 여행을 커버합니다.
  • 3일: 7일권(costs[1] = $7)을 구매하여 3일부터 9일까지의 여행을 모두 커버합니다. 이로써 4, 6, 7, 8일의 여행이 한 번에 포함됩니다.
  • 20일: 다시 1일권(costs[0] = $2)을 구매하여 20일 여행을 커버합니다.

따라서 총 지출은 $2 + $7 + $2 = $11이 됩니다.

동적 계획법(DP)을 이용한 접근 방식

이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 날짜별로 여행을 마치는 데 드는 최소 비용을 순차적으로 계산하는 것입니다. 알고리즘의 단계는 다음과 같습니다.

  1. 크기가 366인 dp 배열을 생성합니다. dp[i]는 i일까지의 여행을 마치는 데 필요한 최소 비용을 의미합니다.
  2. j := 0으로 초기화합니다. (days 배열을 순회하기 위한 인덱스)
  3. i를 1부터 365까지 반복하면서 다음을 수행합니다.
    • dp[i] := costs[0] + dp[i - 1]로 초기화합니다. (1일권 구매 시나리오)
    • i - 7 >= 0이라면, dp[i] := min(dp[i - 7] + costs[1], dp[i])로 갱신합니다. (7일권 구매 시나리오)
    • i - 30 >= 0이라면, dp[i] := min(dp[i - 30] + costs[2], dp[i])로 갱신합니다. (30일권 구매 시나리오)
    • j가 days 배열의 크기 미만이고 days[j] == i라면 j를 1 증가시킵니다. 해당 날짜에 여행 계획이 없다면 dp[i] := min(dp[i], dp[i - 1])로 설정합니다.
  4. 최종적으로 dp[365]를 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector <int> dp(366);
        int j = 0;
        for(int i = 1; i < 366; i++){
            dp[i] = costs[0] + dp[i - 1];
            if(i - 7 >= 0){
                dp[i] = min(dp[i - 7] + costs[1], dp[i]);
            }
            if(i - 30 >= 0){
                dp[i] = min(dp[i - 30] + costs[2], dp[i]);
            }
            if(j < days.size() && days[j] == i){
                j++;
            }else
               dp[i] = min(dp[i], dp[i - 1]);
        }
       return dp[365];
    }
};
main(){
    vector<int> v = {1,4,6,7,8,20};
    vector<int> v1 = {2,7,15};
    Solution ob;
    cout << (ob.mincostTickets(v, v1));
}

입력

[1,4,6,7,8,20]
[2,7,15]

출력

11

마무리

이 알고리즘은 1년(365일) 전체를 한 번씩만 순회하므로 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)입니다. 여행하지 않는 날에는 이전 날의 최소 비용을 그대로 가져오고, 여행하는 날에는 1일권, 7일권, 30일권 중 가장 유리한 선택을 동적 계획법으로 비교함으로써 전체 여행의 최소 비용을 보장할 수 있습니다.