. 티켓 최소 비용

983. 티켓 최소 비용

난이도:중

주제: 배열, 동적 프로그래밍

당신은 1년 전에 기차 여행을 계획했습니다. 일년 중 여행할 날짜는 정수 배열 날짜로 제공됩니다. 각 일은 1부터 365까지의 정수입니다.

기차표는 세 가지 방법으로 판매됩니다.

• 1일 패스는 [0]달러에 판매됩니다.
• 7일 패스는 [1]달러에 판매되며
• 30일 이용권은 [2]달러에 판매됩니다.

패스를 사용하면 해당 날짜만큼 연속 여행할 수 있습니다.

• 예를 들어 2일차에 7일 패스를 받으면 2일, 3일, 4일, 5일, 6일, 7일, 8일 등 7일 동안 여행할 수 있습니다.

주어진 날짜 목록에서 매일 여행하는 데 필요한 최소 달러를 반환합니다.

예 1:

• 입력:일 = [1,4,6,7,8,20], 비용 = [2,7,15]
• 출력: 11
• 설명: 예를 들어 여행 계획에 따라 여행할 수 있는 패스를 구입하는 한 가지 방법은 다음과 같습니다.
  • 첫째 날에 비용[0] = 2달러로 1일 이용권을 구입했는데, 이는 1일차에 해당됩니다.
  • 3일차에 3일, 4일, ..., 9일에 해당하는 비용[1] = $7의 7일 패스를 구입했습니다.
  • 20일에 20일에 해당하는 비용[0] = $2의 1일 이용권을 구입했습니다.
  • 총 11달러를 지출하여 여행 기간 전체를 충당했습니다.

예 2:

• 입력:일 = [1,2,3,4,5,6,7,8,9,10,30,31], 비용 = [2,7,15]
• 출력: 17
• 설명: 예를 들어 여행 계획에 따라 여행할 수 있는 패스를 구입하는 한 가지 방법은 다음과 같습니다.
  • 첫째 날에 1일, 2일, ..., 30일에 해당하는 비용[2] = $15의 30일 패스를 구입했습니다.
  • 31일에 31일에 해당하는 비용[0] = $2의 1일 이용권을 구입했습니다.
  • 여행 기간 동안 총 17달러를 지출하셨습니다.

제약조건:

• 1
• 1 <= 일[i] <= 365
• 일은 엄격하게 증가하는 순서입니다.
• costs.length == 3
• 1 <= 비용[i] <= 1000

해결책:

문제는 연중 특정 날짜에 여행하는 데 필요한 최소 비용을 결정하는 것입니다. 문제는 1일권, 7일권, 30일권의 세 가지 유형의 여행 패스를 제공하며 각각 특정 비용이 적용됩니다. 목표는 이 패스를 사용하여 모든 여행 기간을 충당할 수 있는 가장 저렴한 방법을 찾는 것입니다. 이 작업을 수행하려면 동적 프로그래밍을 사용하여 최소 비용을 효율적으로 계산해야 합니다.

핵심사항

• 동적 프로그래밍(DP): 동적 프로그래밍을 사용하여 매일 최소 비용을 추적하고 있습니다.
• 여행 날짜: 여행 날짜는 엄격하게 오름차순으로 제공되므로 여행해야 하는 날짜를 정확히 알 수 있습니다.
• 세 가지 유형의 패스: 날짜 배열의 각 날짜 d에 대해 현재 날짜 d에 해당하는 패스 구매 비용을 고려하여 최소 비용을 계산합니다.
  • 1일권: 비용은 전날 비용(dp[i-1])에 1일권 비용(costs[0])을 더한 금액입니다.
  • 7일권: 비용은 d로부터 7일 이내인 가장 최근 날의 비용에 7일권의 비용(비용[1])을 더한 금액입니다.
  • 30일 패스: 비용은 d로부터 30일 이내인 가장 최근 날짜의 비용에 30일 패스 비용(비용[2])을 더한 금액입니다.
• 기본 사례: 여행을 하지 않는 날의 최소 비용은 0입니다.

접근하다

1. DP 배열: DP 배열 dp[]를 사용합니다. 여기서 dp[i]는 i일까지의 모든 여행 일수에 필요한 최소 비용을 나타냅니다.
2. DP 배열 채우기: 1부터 365까지 매일:
   • 해당 날짜가 여행일인 경우 다음을 고려하여 최소 비용을 계산합니다.
     • 1일권 사용 비용
     • 7일권 사용 비용
     • 30일 이용권 사용 비용
   • 여행일이 아닌 경우 해당일의 비용은 전날과 동일합니다(dp[i] = dp[i-1]).
3. 최종 답변: DP 배열을 채운 후 여행 가능한 모든 날짜를 포함하는 최소 비용이 dp[365]에 저장됩니다.

계획

1. 크기가 366인 배열 dp[]를 초기화합니다(최대 365일까지 처리하기 위해 하나 추가).
2. 0일에는 비용이 없으므로 dp[0]을 0으로 설정합니다.
3. travelDays 세트를 생성하면 특정 날짜가 여행일인지 빠르게 확인할 수 있습니다.
4. 1부터 365까지 매일 반복합니다.
   • 여행일인 경우 패스 종류별로 고려하여 최소 비용을 계산하세요.
   • 그렇지 않은 경우 전날 비용을 이월하세요.
5. dp[365]에 값을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 983. 티켓 최소 비용

<?php
/**
 * @param Integer[] $days
 * @param Integer[] $costs
 * @return Integer
 */
function mincostTickets($days, $costs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$days1 = [1, 4, 6, 7, 8, 20];
$costs1 = [2, 7, 15];
echo mincostTickets($days1, $costs1); // Output: 11

$days2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs2 = [2, 7, 15];
echo mincostTickets($days2, $costs2); // Output: 17
?>




<h3>
  
  
  설명:
</h3>

<ul>
<li>알고리즘은 1년 중 매일(365일) 반복됩니다.</li>
<li>각 여행일에 대해 다음 중 어느 것이 더 저렴한지 고려하여 비용을 계산합니다.

<ul>
<li>1일권을 구매하세요(전날 가격에 1일권 가격을 더함).</li>
<li>7일 패스를 구매하세요(7일 패스 비용을 추가하고 지난 7일 동안의 여행 비용을 고려).</li>
<li>30일 패스를 구매하세요(30일 패스 비용을 더하고 지난 30일 동안의 여행 비용을 고려함).</li>
</ul>


</li>

<li>여행일이 아닌 경우 비용은 전날과 동일합니다.</li>

</ul>

<h3>
  
  
  예제 연습
</h3>

<h4>
  
  
  예시 1:
</h4>

<p><strong>입력:</strong><br>
</p>

<pre class="brush:php;toolbar:false">$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];

• 1일차: 2달러에 1일 이용권을 구매하세요.
• 4일차: 7일권을 $7에 구매하세요(4~9일 포함).
• 20일차: 2달러에 1일 패스를 추가로 구매하세요.

총 비용 = $2 $7 $2 = $11.

예시 2:

입력:

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

• 1일차: 30일권을 $15에 구매하세요(1일부터 30일까지 포함).
• 31일차: 1일 이용권을 $2에 구매하세요.

총 비용 = $15 $2 = $17.

시간 복잡도

해당 솔루션의 시간 복잡도는 O(365)이며, 연중 내내 반복하고 있으며 매일 일정한 시간 작업(여행 날짜 확인 및 DP 업데이트)을 수행합니다. 정렬). 따라서 솔루션은 일수에 비례하여 선형 시간으로 실행됩니다.

예제 출력

예시 1:

$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 11

예시 2:

$days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 17

동적 프로그래밍을 사용하여 여행 일수에 필요한 최소 비용을 효율적으로 계산하는 솔루션입니다. 며칠 동안 반복하고 가능한 모든 패스(1일, 7일, 30일)를 고려하여 알고리즘은 패스 구매를 위한 최적의 전략을 찾습니다. 시간 복잡도는 일수 기준으로 선형이므로 문제 제약 조건에 적합합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 티켓 최소 비용의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!