[ SWEA 4050 ] 재관이의 대량할인 (C++)

SWExpertAcademy의 재관이의 대량할인(4050) 문제이다.

[ 문제풀이 ]

1) 3벌씩 옷을 묶어서 사면 그 중 가장 저렴한 옷을 계산하지 않고 살 수 있는 세일을 진행할 때, 재관이가 내야할 최소금액을

    찾는 것이 문제이다.

    본인의 구현방법은 다음과 같다. 먼저 모든 가격을 더해서 전체 가격을 구해본다. 그리고 이 전체 가격에서 빼줘야 하는데

    가격이 높은 것들을 높은것끼리 묶어주는 것이 가장 많이 가격을 뺄 수 있다.

    예를 들어서 이런 경우를 생각해보자.

    옷의 가격이 2, 6, 5, 4, 6, 3 이라고 했을 때, 만약 이를 (6, 6, 2) , (5, 4, 3) 으로 묶게 되면 2원 + 3원 총 5원의 할인밖에

    받지 못한다. 하지만 이를 (6, 6, 5), (4, 3, 2) 로 묶게 되면 5원 + 2원으로 총 7원의 할인을 받게 된다.

    즉, 가장 많은 세일을 받기 위해서는 가장 비싼 것들로 3개씩 묶어준 후, 그 중에서 가장 싼 것을 빼주면 된다.

    

    본인은 이 과정을 위해 주어진 가격들을 내림차순으로 정렬을 시켜주었다. 정렬을 시켜준 후, 3번째 옷들만 빼주었다.

    3번째 옷들만 빼준 이유는 정렬을 하고 3개씩 묶게 되면 가장 비싼것들부터 3개씩 묶일 것이고 그 중에서 가장 싼 값은

    그 묶음에서 3번째 값일 것이기 떄문이다.

    위의 예를 그대로 가져와서 다시한번 설명하면 2, 6, 5, 4, 6, 3을 내리참순으로 정렬하게 되면

    6, 6, 5, 4, 3, 2가 되고, 이를 3개씩 묶어보면 (6, 6, 5) , (4, 3, 2)가 된다. 즉, 이 상태에서 3번째 값들인 5원과 2원을

    전체가격에서 빼준것이 최소 금액이 되는 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N, Answer;
int Arr[MAX];
 
bool Sort_Standard(int A, int B)
{
    if (A > B) return true;
    return false;
}
 
void Initialize()
{
    memset(Arr, 0, sizeof(Arr));
    Answer = 0;
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
// 6 4 5 5 5 5
// 4 5 5 5 5 6 
void Solution()
{
    // 가장 비싼것들 끼리 묶어야 되고 안 묶이는 놈은 가장 싼놈들 중 하나여야 한다.
    // 6 5 5 5 5 4
    int Sum = 0;
    for (int i = 1; i <= N; i++)
    {
        Sum = Sum + Arr[i];    // 총합을 구해놓고
    }
    // 6 5 5 5 5 4 3
    sort(Arr + 1, Arr + N + 1, Sort_Standard);
    for (int i = 1; i <= N; i = i + 3)
    {
        Sum = Sum - Arr[i + 2];
    }
    Answer = Sum;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}