출처
ACM-ICPC Asia Regional - Daejeon (링크)
BAEKJOON Online Judge (링크)
문제이해
1회에 1$짜리 버스 티켓과 2$짜리 기차 티켓이 있다.
그리고 1일, 7일, 30일 무제한 이용권이 있는데, 여기서는 버스티켓과, 버스와 기차를 모두 탈 수 있는 티켓으로 나뉜다.
총 여행한 날짜와 각각의 날에 버스와 기차를 이용할 횟수가 입력으로 주어졌을 때 제시된 티켓들을 조합하여 티켓 값의 최소비용을 구하는 문제이다.
문제접근
d[i]를 i일까지 여행했을 때 든 최소비용으로 정의한다. 그리고 하루 전까지 계산한 최소비용 d[i-1]에 오늘 탈 비용을 더하면 되는데, 7일권과 30일권 티켓도 있으므로 7일전과 30일전에서 각각 7일과 30일 티켓을 구입하여 올 경우도 생각해야 한다. 그러면 다음과 같이 7개의 선택지를 비교하여 min값을 구할 수 있다.
- d[i-1] + 버스 낱개 + 기차 낱개 구입비용
- d[i-1] + 버스 하루이용권 + 기차 낱개 구입비용
- d[i-1] + 하루이용권 구입비용
- d[i-7] + 버스 7일권 + 7일간 기차 최소비용
- d[i-7] + 7일권 구입비용
- d[i-30] + 버스 30일권 + 30일간 기차 최소비용
- d[i-30] + 30일권 구입비용
주의할 점은 30일 버스티켓을 이용하고 있는 도중에도 7일짜리 버스+기차 티켓을 추가로 사는 것이 이득일 때가 있다는 것이다.
이제 위에서 진하게 표시한 '7일간 기차 최소비용'과 '30일간 기차 최소비용'을 구하는 것이 문제인데,
전자를 보면 7일권과 1일권의 가격 차이 때문에 버스 7일이용권을 구매한 상태에서, 버스+기차 하루이용권을 구매하는 것은, 7일간의 모든 날짜를 하루이용권만 가지고 계산하는 것보다 비용이 같거나 더 든다. 따라서 7일간 기차이용권을 낱개구매하는 것만 고려하면 된다.
30일간 기차 최소비용은 슬라이딩 윈도우를 사용하여, 하루이용권을 구매해야 이득인 연속된 날짜가 7일 이상 있는지 확인하여 할인차액(6$)를 뺀다.
구현
최대 날짜 수가 10000일인데, 길이가 30인 슬라이딩 윈도우를 사용할 것이므로 조건을 간단히 하기 위해 배열 길이를 10060으로 선언하여 구현하였다.
기차를 탄 횟수도 저장이 필요하여 역시 10060길이로 선언해서 배열 용량으로 총 20120*4 바이트를 사용하였다.
코드
https://github.com/tibyte/algorithm-problems/blob/master/baekjoon/10456.cpp