백준] 15720 - 카우버거(중앙대 CodeRace 2018)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에는 주문한 버거의 갯수 B, 사이드 메뉴의 갯수 C, 음료의 갯수 D가 공백을 사이에 두고 순서대로 주어진다. (1 ≤ B, C, D ≤ 1,000)

둘째 줄에는 각 버거의 가격이 공백을 사이에 두고 주어진다.

셋째 줄에는 각 사이드 메뉴의 가격이 공백을 사이에 두고 주어진다.

넷째 줄에는 각 음료의 가격이 공백을 사이에 두고 주어진다.

각 메뉴의 가격은 100의 배수이며, 10000원을 넘지 않는다.

출력

첫째 줄에는 세트 할인이 적용되기 전 가격을 출력한다.

둘째 줄에는 세트 할인이 적용된 후의 최소 가격을 출력한다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
	int b, c, d, tmp, i;
	int burger[1000], side[1000], drink[1000];
	int sum = 0, ans = 0;
	cin >> b >> c >> d;
	for (i = 0; i < b; i++)
	{
		cin >> burger[i];
		sum += burger[i];
	}
	for (i = 0; i < c; i++)
	{
		cin >> side[i];
		sum += side[i];
	}
	for (i = 0; i < d; i++)
	{
		cin >> drink[i];
		sum += drink[i];
	}

	sort(burger, burger + b);
	sort(side, side + c);
	sort(drink, drink + d);

	for (i = 0; b - i >= 1 && c - i >= 1 && d - i >= 1; i++)
	{
		ans += (burger[b - 1 - i] + side[c - 1 - i] + drink[d - 1 - i])*0.9;
	}
	for (int j = 0; j < b - i; j++)
		ans += burger[j];
	for (int j = 0; j < c - i; j++)
		ans += side[j];
	for (int j = 0; j < d - i; j++)
		ans += drink[j];
	cout << sum << endl << ans;
}

Tip

그리디로 접근하자. 햄버거, 사이드 메뉴, 음료를 모두 정렬해서 비싼 것들부터 우선적으로 세트메뉴로 만드는 방식으로 문제를 풀면 된다.