[SWEA] 7794 동환이의 알뜰살뜰

출처: SWEA

Approach

문제에서도 명시되어 있지만 할인금액은 아래와 같이 계산할 수 있다.

1% → 0.99

2% → 0.98

3% → 0.97

ex) 100만원, 3% 할인 적용 → 100 × 0.97 = 97만원

      36만원, 2% + 3% 할인 쿠폰 적용 → 36 × 0.98 × 0.97 = 34.2216만원

 

구조체 배열 coupon[]에 할인 정보 저장

ex) 상품가격 = 100, 쿠폰 가격 = 1, 할인율 = 2

        → {쿠폰 가격,  쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {1, 0.97, 2} 

ex) 상품가격 = 100, 쿠폰 가격 = 2, 할인율 = 2

        → {쿠폰 가격,  쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {2, 0.97, 1} 

▶ 동일한 할인율에서 쿠폰 가격대비 더 싼 것을 선택해야 한다.

    {쿠폰 가격 = 1, 할인율 = 2} > {쿠폰 가격 = 2, 할인율 = 2}

 

① 가성비 기준으로 정렬

② Greedy하게 쿠폰을 적용했을 때, 정렬된 쿠폰 목록에서

    특정 쿠폰을 적용했을 때, 더 저렴한 구매금액이 나오는지 확인 후 적용

    → 더 저렴한 경우, 해당 쿠폰을 적용

    → 할인이 적용된 누적 구매 금액, 누적 쿠폰 금액을 갱신해준다.

    (* 쿠폰 가성비에 따라 정렬했기에 Greedy하게 수행 가능)

---

#include <stdio.h>
const int MAX_N = 50;
struct Coupon
{
    int price;
    double rate, eff;
}coupon[MAX_N], trr[MAX_N];
int CCM; // Cumulative Coupon Amount (누적 쿠폰 구매 금액)
int TC, N, itemPrice, couponPrice, rate;
double ans, pivot, totalCost;

void mergeSort(int start, int end) 
{
    // 0. base condition
    if (start >= end) return;
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (coupon[i].eff > coupon[j].eff)
            trr[k++] = coupon[i++];
        else
            trr[k++] = coupon[j++];
    }
    while (i <= mid) trr[k++] = coupon[i++];
    while (j <= end) trr[k++] = coupon[j++];
    // 4. copy
    for (i = start; i <= end; ++i) {
        coupon[i] = trr[i];
    }
}

void input()
{
    scanf("%d %d", &N, &itemPrice); // 쿠폰 개수, 게임기 가격
    for (int i = 0; i < N; ++i)
    {
        scanf("%d %d", &couponPrice, &rate);
        // 쿠폰 가격, 할인율(백분율), 가성비
        coupon[i] = { couponPrice, (100 - rate) * 0.01, rate / double(couponPrice)  };
    }
}

double solve()
{
    CCM = 0; // 누적 쿠폰 구매 가격
    ans = itemPrice; // 쿠폰 적용 없이 원가 그대로 구매 금액
    totalCost = itemPrice; // 지금까지 누적된 상품 금액 (할인 적용 포함)
    for (int i = 0; i < N; ++i)
    {
        // 기준(pivot) = (지금까지 쿠폰 적용했을 때 구매 금액 * coupon[i] 할인율)
        //               + (지금까지 적용한 쿠폰 구매 금액 + coupon[i]  구매 금액)
        pivot = (totalCost * coupon[i].rate + CCM + coupon[i].price);
        // 더 나은 가격인 경우 갱신
        if (ans > pivot) {
            ans = pivot;
            CCM += coupon[i].price; // 누적 쿠폰 구매 금액 갱신
            totalCost *= coupon[i].rate; // 쿠폰 적용된 누적 구매 금액 갱신
        }
    }
    return ans;
}

int main(void)
{
    // freopen("input.txt", "r", stdin);
    
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; ++tc)
    {
        input();
        mergeSort(0, N - 1); // (가성비 기준) 쿠폰 정렬
        printf("#%d %lf\n", tc, solve());
    }
    return 0;
}