통신 사업자가 k 달러의 고정 가격으로 n개의 OTT 콘텐츠 제공자에게 액세스를 제공하는 "올인원"이라는 서비스를 도입했다고 가정합니다. 이제 OTT 플랫폼에 직접 가입해야 하는 경우 각 플랫폼에 개별 금액을 지불해야 합니다. 우리는 항상 모든 플랫폼에 대한 구독이 필요하지 않으므로 해당 서비스를 비용 효율적으로 사용하는 방법을 찾아야 합니다. 플랫폼 i의 서비스가 필요한 시작 월은 배열 start_month에 제공되고 종료 월은 배열 end_month에 제공됩니다. 플랫폼에 가입하는 데 필요한 가격은 배열 가격[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입니다.
단계
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
Define an array pairArray for initialize i := 0, when i < n, update (increase i by 1), do: insert pair(start_month[i], price[i]) at the end of pairArray insert pair(end_month[i] + 1, -price[i]) at the end of pairArray sort the array pairArray pre := 0 c := 0 res := 0 for each element p in pairArray, do: day := first element of p - pre res := res + minimum of (k, c) c := c + second element of p pre := first element of p return res
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<int> res;
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