[SW Expert Academy] 4050. 재관이의 대량 할인

4050. 재관이의 대량 할인

클릭시 문제로 이동합니다!

SW Expert Academy는 저작권이 걸려있기 때문에 링크로 대체합니다!

어떻게 풀까?

생각보다 직관적으로 풀 수 있습니다.

먼저 알아야 할 것은

가장 적은 돈을 내기 위해서는 가장 값이 비싼 물건들을 할인 받아야 한다는 것이죠!

즉, 더 비싼 물건 2 개를 골라야 한다는 것입니다!

그렇다면, 어떤 물품의 집합에서 3 개를 골라서 가장 많이 할인을 받는 방법을 생각해봅시다!

당연하게도 가장 비싼 물건 3개를 하나의 조합으로 선택하고, 이 중에서 가장 싼 것을 할인받는 것이죠!

그리고.. 나머지도 마찬가지 방법으로 해결될 것입니다.

결국 이 문제는 정렬을 해서 3번째 물건의 가격들을 빼면 풀리는 문제입니다!

코드

#include<cstring>
#include<cstdio>
 
int len, price[100000], temp[100000];
 
void mergeSort(int left, int m, int right) {
    int l = left, r = m + 1, k = l;
 
    while (l <= m && r <= right) {
        if (price[l] > price[r]) {
            temp[k++] = price[l++];
        }
        else {
            temp[k++] = price[r++];
        }
    }
 
    while (l <= m) temp[k++] = price[l++];
    while (r <= right) temp[k++] = price[r++];
 
    for (int i = left; i <= right; i++) {
        price[i] = temp[i];
    }
}
 
void merge(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
 
        merge(l, m);
        merge(m + 1, r);
 
        mergeSort(l, m, r);
    }
}
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d\n", &len);
 
        long long sum = 0;
 
        for (int i = 0; i < len; i++) {
            scanf("%d \n", &price[i]);
            sum += (long long)price[i];
        }
 
        merge(0, len - 1);
 
        //3번째 마다의 물건 가격을 빼준다.
        for (int i = 2; i < len; i += 3) {
            sum -= (long long)price[i];
        }
        printf("#%d %lld\n", tc, sum);
    }
 
    return 0;
}

여담

정렬을 해야하기 때문에 시간복잡도는 

입니다.

아참! 문제의 최대값이 10^10이기 때문에 int로는 표현이 불가능할 수도 있습니다!

long long으로 해결합시다!