문제 소개
통신사가 '올인원(all-in-one)'이라는 신규 서비스를 출시했다고 가정해 보겠습니다. 이 서비스에 가입하면 n개의 OTT 콘텐츠 제공업체를 모두 고정 요금 k달러로 이용할 수 있습니다. 반면, 각 OTT 플랫폼에 개별적으로 직접 구독하려면 플랫폼마다 별도의 요금을 지불해야 합니다.
모든 플랫폼을 매월 구독할 필요는 없기 때문에, 필요한 기간에 맞춰 가장 비용 효율적으로 서비스를 이용하는 방법을 찾아야 합니다. i번째 플랫폼의 구독 시작 월은 배열 start_month에, 종료 월은 배열 end_month에 담겨 있으며, 각 플랫폼의 구독료는 price[i]로 주어집니다. 목표는 필요한 조건에 맞춰 모든 플랫폼을 구독할 때 지불해야 하는 최소 금액을 구하는 것입니다.
예를 들어 입력이 n = 3, k = 10, start_month = {1, 2, 1}, end_month = {3, 3, 2}, price = {5, 7, 8}이라면 출력은 30이 됩니다.
총 3개월 동안 구독이 필요합니다.
- 첫째 달: 1번과 3번 플랫폼 구독이 필요합니다. 개별 구독 시 총 5 + 8 = 13달러지만, 올인원 패키지는 10달러면 충분합니다.
- 둘째 달: 세 플랫폼 모두 필요하며 개별 구독료는 총 20달러입니다. 올인원 패키지로 10달러만 내면 됩니다.
- 셋째 달: 구독료 총액은 12달러지만, 역시 10달러만 지불하면 됩니다.
따라서 총비용은 10 + 10 + 10 = 30입니다.
풀이 접근 방식
이 문제는 스위핑(sweeping) 기법으로 해결할 수 있습니다. 각 플랫폼의 구독이 시작되는 시점에는 해당 구독료를 더하고, 종료 월의 다음 달에는 구독료를 차감하면서 특정 시점에 활성화된 구독료의 총합을 추적합니다. 그리고 각 구간마다 '현재 활성 구독료 총합'과 '올인원 패키지 가격 k' 중 작은 값을 선택해 누적하면 됩니다.
구체적인 절차는 다음과 같습니다.
pairArray 배열을 정의한다
i := 0부터 i < n까지 i를 1씩 증가시키며 반복:
pairArray 끝에 (start_month[i], price[i]) 페어를 삽입
pairArray 끝에 (end_month[i] + 1, -price[i]) 페어를 삽입
pairArray를 오름차순으로 정렬한다
pre := 0
c := 0
res := 0
pairArray의 각 원소 p에 대해 반복:
day := p의 첫 번째 값 - pre
res := res + min(k, c) × day
c := c + p의 두 번째 값
pre := p의 첫 번째 값
res를 반환한다C++ 구현 예시
다음 구현 예시를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k, int start_month[], int end_month[], int price[]){
vector<pair<int, int>> pairArray;
for(int i = 0; i < n; i++) {
pairArray.push_back(make_pair(start_month[i], price[i]));
pairArray.push_back(make_pair(end_month[i] + 1, -price[i]));
}
sort(pairArray.begin(), pairArray.end());
int pre = 0;
int c = 0;
int res = 0;
for(auto p : pairArray) {
int day = p.first - pre;
res += min(k, c) * day;
c += p.second;
pre = p.first;
}
return res;
}
int main() {
int n = 3, k = 10, start_month[] = {1, 2, 1}, end_month[] = {3, 3, 2}, price[] = {5, 7, 8};
cout<< solve(n, k, start_month, end_month, price);
return 0;
}입력
3, 10, {1, 2, 1}, {3, 3, 2}, {5, 7, 8}출력
30
동작 원리 정리
각 구독은 시작 월에 +price[i], 종료 월 다음 달에 -price[i] 이벤트를 생성합니다. 이벤트를 시간순으로 정렬한 뒤 순회하면, 변수 c에는 현재 시점에 활성화된 구독료의 합계가 유지됩니다. 인접한 두 이벤트 사이의 구간이 day개월 지속된다면, 해당 구간의 비용은 min(k, c) × day가 됩니다. 즉, 매 구간마다 개별 구독과 올인원 패키지 중 더 저렴한 쪽이 자동으로 선택되므로 전체 최소 비용이 보장됩니다.