[ 백준 16917 ] 양념 반 후라이드 반 (C++)

백준의 양념 반 후라이드 반(16917)  문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 치킨를 구매하는데 드는 최소비용을 구해야 하는 문제이다. 사실 처음보고 문제에 접근하는 방법이 바로 떠올라서

   구현하기가 어렵지 않았다.

   그 방법은 이렇다. 먼저, 반반치킨을 2마리(양념 1마리, 후라이드 1마리가 되도록) 사는 가격과,

   양념 1마리 + 후라이드 1마리 사는 가격을 비교해서 만약 후자가 더 작다면(양념 1마리 + 후라이드 1마리 가격이 더 싸다면)

   굳이 반반치킨을 구매할 필요 없이, 구매하고자 하는 모든 치킨들을 각각 구매하면 최소값이 된다.

   반대인 경우에는, 최소 마리만큼 반반치킨을 사버리고 남은 치킨을 각자 구매로 계산을 해 보았다.

   이런 경우를 예로 들어보겠다.

   양념 1마리 가격 : 1000원

   후라이드 1마리 가격 : 2000 원

   반반치킨 1마리 가격 : 1300원

   사고자 하는 양념치킨 수 : 3마리

   사고자 하는 후라이드 치킨 수 : 5마리

   라고 할 경우, (1000 + 2000 = 3000) 이 (1300 * 2 = 2600) 보다 싸기 때문에 이 경우에는 반반치킨을 사는 것이

   더 최소의 금액으로 구매할 수 있다는 것을 알 수 있다.

   그럼, 2600원으로 3마리를 사버리는 것이다. 그렇게 되면 양념치킨은 3마리 모두 구매가 끝나고, 후라이드 치킨은

   아직 2마리가 남아있다. 이 때, 2마리를 후라이드의 가격으로 구매해 버리는 방식으로 구현했다.

   하지만 틀렸습니다 를 받게 되었다.

   그럼 이 방법이 왜 틀렸는지 한번 알아보자. 사실 문제를 다시한번 읽는다고 이 부분을 찾아내기는 힘들 것 같다.

   그렇다면 예제입력3을 한번 봐보도록 하자.

   예제입력 3을 말로 풀어쓰면 다음과 같다.

   양념치킨 1마리의 가격 : 1500원

   후라이드치킨 1마리의 가격 : 2000원

   반반치킨 1마리의 가격 : 500원

   사고자 하는 양념치킨의 수 : 3마리

   사고자 하는 후라이드 치킨의 수 : 2마리

   본인이 위에서 들었던 예와 아주 똑같은 경우이다. 따라서 본인은 본인이 설명한대로

   1000원(반반치킨을 한마리로 만들기 위한 가격)으로 90000마리를 구매한다. 그럼 90000000원이 되고,

   남은 후라이드 치킨 10000마리를 2000원으로 구매하게 되면 20000000원이 된다.

   즉, 최소값이 이 2개의 값을 더한 110000000이 된다. 하지만 정답은? 100000000원이다.

   왜그럴까??? 문제에서 요구하는 것은 이것이다.

   "양념치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하는 비용의 최소값 출력"

   쉽게 이야기 하면 양념치킨을 정확하게 X마리만 딱 사고, 후라이드 치킨을 정확하게 Y마리를 딱 살 때 최소값이

   아니라, 최소로 살 때의 최소값을 구하는 것이다.

   즉, 초과해서 구매해도 된다는 이야기이다.

   이게 무슨이야기일까?? 다시한번 문제를 풀어보자.

   1000원으로 90000마리를 구매해서 나온 90000000원에서, 남은 후라이드 치킨 10000마리를, 후라이드로 구매하는 것이

   아니라 반반치킨으로 구매해버린다면?? 1000원으로 10000마리를 더 사야 하므로 10000000 원이 되게 된다.

   그럼 합치게 되면? 바로 정답인 100000000 원이 된다.

   이것이 문제의 가장 큰 함정인 것 같다. 즉 우리는 정확하게 X, Y마리를 샀을 때의 경우를 보는 것이 아니라,

   최소 X, Y마리 이므로 초과해도 된다는 것을 주의해줘야 할 것 같다.

   구현에 대한 부분은 소스코드를 참고하도록 하자.

[ 소스코드 ]

#include<iostream>
#include<set>
 
typedef long long ll;
#define endl "\n"
#define INF 987654321
using namespace std;
 
int Fried_Cost, Spicy_Cost, Half_Cost, Fried_Num, Spicy_Num;
int Answer;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> Fried_Cost >> Spicy_Cost >> Half_Cost >> Fried_Num >> Spicy_Num;
    Half_Cost = Half_Cost * 2;
}
 
 
void Solution()
{
    int Temp_Answer = 0;
    int Temp_Answer2 = 0;
 
    if (Fried_Cost + Spicy_Cost > Half_Cost)
    {
        int Min_Chicken;
 
        if (Fried_Num < Spicy_Num)
        {
            Min_Chicken = Fried_Num;
 
            int Temp = 0;
            while (Min_Chicken--)
            {
                Temp = Temp + Half_Cost;
                Spicy_Num--;
            }
 
            Temp_Answer = Temp;
            Temp_Answer2 = Temp;
 
            int Cnt = Spicy_Num;
            while (Spicy_Num--)    Temp_Answer = Temp_Answer + Spicy_Cost;
            while (Cnt--)    Temp_Answer2 = Temp_Answer2 + Half_Cost;
 
            Answer = Min(Temp_Answer, Temp_Answer2);
        }
        else
        {
            Min_Chicken = Spicy_Num;
 
            int Temp = 0;
            while (Min_Chicken--)
            {
                Temp = Temp + Half_Cost;
                Fried_Num--;
            }
 
            Temp_Answer = Temp;
            Temp_Answer2 = Temp;
 
            int Cnt = Fried_Num;
            while (Fried_Num--) Temp_Answer = Temp_Answer + Fried_Cost;
            while (Cnt--) Temp_Answer2 = Temp_Answer2 + Half_Cost;
 
            Answer = Min(Temp_Answer, Temp_Answer2);
        }
    }
    else
    {
        Answer = Fried_Cost * Fried_Num + Spicy_Num * Spicy_Cost;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}