Dec 31, 2024

983. Minimum Cost For Tickets

내 코드

초기 아이디어의 문제점. > 7일차나 30일 티켓이 1일 티켓보다 더 싸면 그것을 사야 하는데, 고려가 없음!!

// 초기 코드
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // [start, start + days - 1]
        // [2, 2 + 7 - 1]
        vector dp(366, vector(3, 1 << 30));
        dp[0][0] = dp[0][1] = dp[0][2] = 0;
        int i{};
        for(int day{1};day<366;++day) {
            if(i < days.size() && days[i] == day) {
                dp[day][0] = getMin(dp[day-1]) + costs[0];
                if(day >= 7) dp[day][1] = getMin(dp[day-7]) + costs[1];
                if(day >= 30) dp[day][2] = getMin(dp[day-30]) + costs[2];
                ++i;
            }
            else {
                dp[day][0] = dp[day -1][0];
                dp[day][1] = dp[day-1][1];
                dp[day][2] = dp[day-1][2];
            }
        }
        int lastDay = days.back();
        return getMin(dp[lastDay]);
    }

    int getMin(vector<int>& day) {
        // return min(begin(day), end(day));
        return min({day[0], day[1], day[2]});
    }
};

GPT

당신의 코드은 Minimum Cost For Tickets 문제를 해결하기 위해 동적 계획법(Dynamic Programming)을 사용하고 있습니다. 전반적으로 접근 방식은 합리적이지만, 몇 가지 문제점과 개선할 수 있는 부분이 있습니다. 주요 문제점과 그에 대한 설명은 다음과 같습니다.

1. 7일 및 30일 패스의 초기 구매 조건 문제

현재 코드에서는 day >= 7 및 day >= 30인 경우에만 7일 및 30일 패스를 구매할 수 있도록 조건을 설정하고 있습니다. 그러나 실제로는 첫 여행일(day = 1)에도 7일 또는 30일 패스를 구매할 수 있으며, 이는 초기 일수(day < 7 또는 day < 30)에도 유효합니다. 따라서 이러한 경우를 고려하지 않으면 최적의 해를 찾지 못할 수 있습니다.

문제점 예시:

예를 들어, 첫 여행일이 day = 1이고 7일 패스의 비용이 더 저렴할 경우, 현재 조건(day >= 7)으로는 7일 패스를 고려하지 않게 됩니다.

2. DP 배열의 상태 관리

현재 DP 배열은 dp[day][0], dp[day][1], dp[day][2]로 3가지 상태를 관리하고 있습니다. 이는 각 패스 유형별로 별도의 최소 비용을 추적하는 방식인데, 이는 패스가 겹치는 상황에서 복잡성을 증가시킬 수 있습니다. 보다 간단하고 효율적인 방법은 각 날에 대한 최소 비용을 하나의 값으로 관리하는 것입니다.

3. 코드 개선 제안

위 문제점을 해결하고 코드의 효율성을 높이기 위해 다음과 같은 개선을 제안합니다:

7일 및 30일 패스의 초기 구매를 허용:
- day >= 7 대신 day >= 1일 때도 7일 패스를 고려하도록 수정합니다.
- 마찬가지로 day >= 30 대신 day >= 1일 때도 30일 패스를 고려하도록 수정합니다.
DP 배열을 단일 값으로 관리:
- 각 날에 대한 최소 비용을 단일 dp[day]로 관리하여 코드의 단순화와 효율성을 높입니다.
불필요한 상태 관리 제거:
- 패스 유형별로 별도의 상태를 관리하지 않고, 단일 최소 비용을 추적합니다.

4. 수정된 코드 예시

아래는 위의 개선 사항을 반영한 수정된 코드입니다:

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        unordered_set<int> daySet(days.begin(), days.end());
        int lastDay = days.back();
        vector<int> dp(lastDay + 1, 0);
        
        for(int day = 1; day <= lastDay; ++day) {
            if(!daySet.count(day)) {
                dp[day] = dp[day-1];
                continue;
            }
            // 비용 계산: 1일, 7일, 30일 패스 중 최소값 선택
            int cost1 = dp[max(0, day - 1)] + costs[0];
            int cost7 = dp[max(0, day - 7)] + costs[1];
            int cost30 = dp[max(0, day - 30)] + costs[2];
            dp[day] = min({cost1, cost7, cost30});
        }
        
        return dp[lastDay];
    }
};

5. 설명

unordered_set 사용: 여행일을 빠르게 조회하기 위해 unordered_set을 사용합니다.
단일 DP 배열: 각 날에 대한 최소 비용을 단일 dp[day]로 관리합니다.
패스 구매 시점 고려: 1일, 7일, 30일 패스를 구매할 수 있는 모든 경우를 고려하여 최소 비용을 계산합니다.
경계 조건 처리: max(0, day - duration)을 사용하여 경계 조건을 처리합니다.

6. 결론

기존 코드에서 주요 문제는 초기 조건 설정과 DP 상태 관리 방식에 있었습니다. 위에서 제안한 수정된 접근 방식을 따르면, 더 간결하고 효율적으로 문제를 해결할 수 있으며, 모든 경우를 올바르게 고려하여 최적의 해를 보장할 수 있습니다.

Solution

Approach 1: Top-Down Dynamic Programming

0ms, 13.18MB
Complexity
- Here, $K$ is the last day we need to travel, the last value in the array days.
- Time Complexity: $O(K)$
- Space Complexity: $O(K)$

class Solution {
public:
    unordered_set<int> isTravelNeeded;
    
    int solve(vector<int>& dp, vector<int>& days, vector<int>& costs, int currDay) {
        // If we have iterated over travel days, return 0.
        if (currDay > days[days.size() - 1]) {
            return 0;
        }
        
        // If we don't need to travel on this day, move on to next day.
        if (isTravelNeeded.find(currDay) == isTravelNeeded.end()) {
            return solve(dp, days, costs, currDay + 1);
        }
        
        // If already calculated, return from here with the stored answer.
        if (dp[currDay] != -1) {
            return dp[currDay];
        }
        
        int oneDay = costs[0] + solve(dp, days, costs, currDay + 1);
        int sevenDay = costs[1] + solve(dp, days, costs, currDay + 7);
        int thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30);
        
        // Store the cost with the minimum of the three options.
        return dp[currDay] = min(oneDay, min(sevenDay, thirtyDay));
    }
    
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // The last day on which we need to travel.
        int lastDay = days[days.size() - 1];
        vector<int> dp(lastDay + 1, -1);
        
        // Mark the days on which we need to travel.
        for (int day : days) {
            isTravelNeeded.insert(day);
        }
        
        return solve(dp, days, costs, 1);
    }
};

GPT

이 코드는 “여행 티켓 최소 비용” 문제를 해결합니다. 주어진 날짜와 세 가지 티켓 비용을 바탕으로, 여행 계획을 충족시키기 위해 필요한 최소 비용을 계산합니다. 이 문제는 동적 프로그래밍(DP) 과 재귀를 사용하여 해결됩니다.

문제 정의

주어진 입력

days: 여행할 날짜가 나열된 정렬된 배열.
costs:
- costs[0]: 1일 티켓 비용.
- costs[1]: 7일 티켓 비용.
- costs[2]: 30일 티켓 비용.

목표

모든 여행 날짜를 충족하기 위한 최소 비용을 계산.

코드 설명

1. 주요 아이디어

DP 배열 dp[currDay]:
- 현재 날짜 currDay에서 여행 계획을 충족하는 데 필요한 최소 비용을 저장.
점화식: $dp[currDay] = \min(\text{1-day cost}, \text{7-day cost}, \text{30-day cost})$ $d p [c u r r D a y] = min (1-day cost, 7-day cost, 30-day cost)$
- 1-day cost: $\text{costs[0]} + dp[currDay + 1]$
- 7-day cost: $\text{costs[1]} + dp[currDay + 7]$
- 30-day cost: $\text{costs[2]} + dp[currDay + 30]$

2. 함수 `solve`

a. 기저 조건

if (currDay > days[days.size() - 1]) {
    return 0;
}

여행이 마지막 날을 초과하면 더 이상 비용이 들지 않으므로 $0$ 반환.

b. 현재 날짜에 여행이 필요한지 확인

if (isTravelNeeded.find(currDay) == isTravelNeeded.end()) {
    return solve(dp, days, costs, currDay + 1);
}

isTravelNeeded는 여행이 필요한 날짜를 저장한 집합.
현재 날짜에 여행이 필요하지 않다면 다음 날짜로 이동.

c. 메모이제이션 확인

if (dp[currDay] != -1) {
    return dp[currDay];
}

이미 계산된 값이 있다면 중복 계산을 방지하기 위해 반환.

d. 점화식 계산

int oneDay = costs[0] + solve(dp, days, costs, currDay + 1);
int sevenDay = costs[1] + solve(dp, days, costs, currDay + 7);
int thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30);

return dp[currDay] = min(oneDay, min(sevenDay, thirtyDay));

1일, 7일, 30일 티켓을 구매했을 때의 최소 비용을 계산.
결과를 dp[currDay]에 저장하고 반환.

3. 함수 `mincostTickets`

a. DP 배열 초기화

int lastDay = days[days.size() - 1];
vector<int> dp(lastDay + 1, -1);

dp 배열은 $0$ 부터 마지막 여행 날짜까지 초기화.

b. 여행 날짜 저장

for (int day : days) {
    isTravelNeeded.insert(day);
}

isTravelNeeded는 여행이 필요한 날짜를 집합으로 저장.

c. 결과 반환

return solve(dp, days, costs, 1);

첫 번째 날부터 재귀 호출을 시작.

시간 및 공간 복잡도

시간 복잡도

재귀 호출:
- 최대 $O(\text{lastDay})$ 번 호출.
- 각 호출은 $O(1)$ 연산.
여행 날짜 저장:
- $O(\text{days.size()})$ .

총 시간 복잡도: $O(\text{lastDay} + \text{days.size()})$

공간 복잡도

DP 배열:
- $O(\text{lastDay})$ .
집합 isTravelNeeded:
- $O(\text{days.size()})$ .

총 공간 복잡도: $O(\text{lastDay} + \text{days.size()})$

작동 예시

입력:

days = [1, 4, 6, 7, 8, 20];
costs = [2, 7, 15];

계산 과정:

여행 날짜 저장: $\text{isTravelNeeded} = \{1, 4, 6, 7, 8, 20\}$
재귀 호출:
- $dp[20]$ : 최소 비용 계산.
- $dp[8]$ , $dp[7]$ , $dp[6]$ : 반복적으로 호출.
최종 결과:
- 최소 비용: $11$ .

출력:

확장 예시

입력:

days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30];
costs = [2, 7, 15];

계산 과정:

재귀 호출:
- $dp[30]$ : 최소 비용 계산.
- 반복적으로 이전 값을 참조하여 계산.
최종 결과:
- 최소 비용: $17$ .

출력:

Approach 2: Bottom-up Dynamic Programming

0ms, 12.82MB
Complexity
- Here, $K$ is the last day we need to travel, the last value in the array days.
- Time Complexity: $O(K)$
- Space Complexity: $O(K)$

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int lastDay = days[days.size() - 1];
        vector<int> dp(lastDay + 1, 0);
        
        int i = 0;
        for (int day = 1; day <= lastDay; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;
                dp[day] = min({dp[day - 1] + costs[0],
                               dp[max(0, day - 7)] + costs[1],
                               dp[max(0, day - 30)] + costs[2]});
            }
        }
     
        return dp[lastDay];
    }
};

GPT

이 코드는 “여행 티켓 최소 비용” 문제를 해결합니다. 주어진 날짜와 세 가지 티켓 비용을 바탕으로, 여행 계획을 충족하기 위한 최소 비용을 계산합니다. 동적 프로그래밍(DP)을 사용하여 효율적으로 해결됩니다.

문제 정의

주어진 입력

days: 여행할 날짜가 정렬된 배열.
costs:
- costs[0]: 1일 티켓 비용.
- costs[1]: 7일 티켓 비용.
- costs[2]: 30일 티켓 비용.

목표

모든 여행 날짜를 충족하기 위한 최소 비용을 계산.

코드 분석

1. 주요 아이디어

DP 배열 dp:
- dp[day]: 특정 날짜 day까지 여행 계획을 충족하는 최소 비용.
점화식:
- 여행하지 않는 날에는 이전 날의 비용을 그대로 유지.
- 여행하는 날에는 세 가지 티켓 비용 중 최소값을 선택:
  $dp[day] = \min(\text{1-day}, \text{7-day}, \text{30-day})$
- 계산식:
  $dp[day] = \min(dp[day - 1] + \text{costs[0]}, \, dp[day - 7] + \text{costs[1]}, \, dp[day - 30] + \text{costs[2]})$

2. 코드 단계별 설명

1. DP 배열 초기화

int lastDay = days[days.size() - 1];
vector<int> dp(lastDay + 1, 0);

lastDay: 여행이 필요한 마지막 날짜.
dp: 0부터 lastDay까지의 비용을 저장하는 배열. 초기값은 0.

2. 여행 비용 계산

int i = 0;
for (int day = 1; day <= lastDay; day++) {
    if (day < days[i]) {
        dp[day] = dp[day - 1];
    } else {
        i++;
        dp[day] = min({dp[day - 1] + costs[0],
                       dp[max(0, day - 7)] + costs[1],
                       dp[max(0, day - 30)] + costs[2]});
    }
}

여행하지 않는 날:
- day < days[i]: 현재 날짜가 여행할 날짜에 포함되지 않음.
- dp[day] = dp[day - 1]: 이전 날의 비용을 그대로 복사.
여행하는 날:
- $\text{1-day 티켓 비용}: dp[day - 1] + \text{costs[0]}$
- $\text{7-day 티켓 비용}: dp[day - 7] + \text{costs[1]}$
- $\text{30-day 티켓 비용}: dp[day - 30] + \text{costs[2]}$
- $dp[day]$ : 위 세 가지 중 최소값.
범위 초과 방지:
- $\text{max(0, day - 7)}$ : 음수 인덱스를 방지하기 위해 $0$ 으로 제한.

3. 결과 반환

return dp[lastDay];

마지막 날까지의 최소 비용을 반환.

시간 및 공간 복잡도

시간 복잡도

DP 배열 계산:
- $O(\text{lastDay})$ : 각 날짜를 한 번씩 순회.
최소값 계산:
- 상수 시간( $O(1)$ ) 연산.

총 시간 복잡도:
$O(\text{lastDay})$

공간 복잡도

DP 배열:
- $O(\text{lastDay})$ .

총 공간 복잡도:
$O(\text{lastDay})$

작동 예시

입력:

days = [1, 4, 6, 7, 8, 20];
costs = [2, 7, 15];

계산 과정:

초기화: $dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0] \quad (\text{크기: } 21)$
날짜별 DP 계산:

`day`	여행 날짜	`dp[day]` 최소 비용
1	O	$dp[1] = \min(dp[0] + 2, dp[0] + 7, dp[0] + 15) = 2$
2	X	$dp[2] = dp[1] = 2$
4	O	$dp[4] = \min(dp[3] + 2, dp[0] + 7, dp[0] + 15) = 4$
6	O	$dp[6] = \min(dp[5] + 2, dp[0] + 7, dp[0] + 15) = 6$
7	O	$dp[7] = \min(dp[6] + 2, dp[0] + 7, dp[0] + 15) = 7$
8	O	$dp[8] = \min(dp[7] + 2, dp[1] + 7, dp[0] + 15) = 9$
20	O	$dp[20] = \min(dp[19] + 2, dp[13] + 7, dp[0] + 15) = 11$

확장 예시

입력:

days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30];
costs = [2, 7, 15];

983. Minimum Cost For Tickets

내 코드

GPT

1. 7일 및 30일 패스의 초기 구매 조건 문제

문제점 예시:

2. DP 배열의 상태 관리

3. 코드 개선 제안

4. 수정된 코드 예시

5. 설명

6. 결론

Solution

Approach 1: Top-Down Dynamic Programming

GPT

문제 정의

주어진 입력

목표

코드 설명

1. 주요 아이디어

2. 함수 solve

a. 기저 조건

b. 현재 날짜에 여행이 필요한지 확인

c. 메모이제이션 확인

d. 점화식 계산

3. 함수 mincostTickets

a. DP 배열 초기화

b. 여행 날짜 저장

c. 결과 반환

시간 및 공간 복잡도

시간 복잡도

공간 복잡도

작동 예시

입력:

계산 과정:

출력:

확장 예시

입력:

계산 과정:

출력:

Approach 2: Bottom-up Dynamic Programming

GPT

문제 정의

주어진 입력

목표

코드 분석

1. 주요 아이디어

2. 코드 단계별 설명

1. DP 배열 초기화

2. 여행 비용 계산

3. 결과 반환

시간 및 공간 복잡도

시간 복잡도

공간 복잡도

작동 예시

입력:

계산 과정:

확장 예시

입력:

출력:

2. 함수 `solve`

3. 함수 `mincostTickets`