16917 양념 반 후라이드 반

https://www.acmicpc.net/problem/16917

16917번: 양념 반 후라이드 반

양념 반 후라이드 반 성공

 

 Bronze III

난이도 제공: solved.ac — 난이도 투표하러 가기

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

1097

652

549

61.000%

문제

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

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

입력

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

출력

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

제한

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

1.양념, 후라이드를, 각각 (양념A, 후라이드B, 반반 C)을 구매하여 X,Y (양념,후라이드)의 최소 개수 이상을

만족하는 최소 가격을 찾는것.

 

2. X,Y최소 개수 이상이므로 만약, x=3 y=2 라고하여도 반반을 구매하여 x=3 y=3을 구매하여 최소가격이

나올 수 있으면 해당 갯수도 만족을 한다고 볼 수 있다.

 

3. X,Y의 제한은 10만, A * X + B * Y = 양념개수 * 양념 가격 + 후라이드 수 * 후라이드 가격 

for( 양념 10만)
 {

  for( 후라이드 10만) 을 탐색으로 일일이 따지면 O(N^2) = 100억으로 시간 초과가 난다.

   {

    }

} 

4. 시작 값을 반반 치킨을 제외하고 AX+BY 가격으로 고정시켜놓고,  반반 치킨 C를 한번씩 구매하면서 10만 번을 탐색
  (반반치킨은 2개 구매하였을때 양념+1, 후라이드+1이 되므로 2개씩 구매하는것을 원칙으로한다. (따라서 가격 2*C))

 

5. 반복문은 반반을 i개씩 구매할때마다  반반 가격 + 양념의 필요갯수 * 양념가격 +  후라이드 필요갯수 * 후라이드가격
 을 확인하며 최소값을 구한다.

 

6. 최소값중에 반반을 구매하지 않아도 될때가 있을 수 있으므로, 최소가격은 양념과 후라이드를 각각 구매하였을때
가격인 AX + BY로 설정 (int ans = X*A + Y*B);

 

#include<iostream>
#include<algorithm>
using namespace std;

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

	solve();
	return 0;
}

void solve()
{
	int sum = 0;
	int ans = X * A + Y * B;
	for (int i = 1; i <= 100000; i++)
	{
		sum = (2 * C*i) + max(0, X - i)*A + (max(0, Y - i)*B);

		if (sum < ans)
			ans = sum;
	}
	cout << ans << '\n';
}