백준 16917번 양념 반 후라이드 반

문제

현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 A원, 후라이드 치킨 한 마리의 가격은 B원, 반반 치킨 한 마리의 가격은 C원이다.

상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다. 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다. 상도가 치킨을 구매하는 금액의 최솟값을 구해보자.

입력

첫째 줄에 다섯 정수 A, B, C, X, Y가 주어진다.

출력

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

제한

• 1 ≤ A, B, C ≤ 5,000
• 1 ≤ X, Y ≤ 100,000

 

반복문으로 브루트포스시에 시간초과 .

그냥 그리디로 풀 수 밖에 없다.

따로만 사는 것, 반반 섞어 사는 것, 반반으로만 사는 것

이 3가지 케이스로 구분하고,

반반으로만 사는 것의 최소비용은 딱 X,Y중 최대 개수인 것에 맞춰서 사는 것이다.

그리고 반반을 섞어 사는 것을 생각해보면 만약 반반으로 사는게 유리하다면 반반으로만 사는것에서 최소가 나올것이고

안사는 것이 유리하다면 따로 사는것에서 최소가 나올것이다.

X,Y중 작은것에 맞춰 반반을 사고 나머지 개수만큼 따로 사는 케이스는 모른다. 따라서 이렇게 분류 해줌. 

만약 작은것에 맞춘 반반 개수보다 반반이 더 많아지는게 유리하다면 결국 반반으로만 사는 케이스가 최소가 됨. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
#include<map>
using namespace std;

int A, B, C, X, Y;
int main(void)
{
	cin >> A >> B >> C >> X >> Y;

	int sum1 = A * X + B * Y; // 따로
	int sum2 = max(X, Y) * 2 * C; // 반반으로만
	
	int sum3 = min(X, Y) * 2 * C;
	int temp = min(X, Y);
	X -= temp;
	Y -= temp;
	sum3 += (X * A + Y * B);

	cout << min(min(sum1, sum2), sum3) << endl;



}