[백준 23559] 밥 (C++)

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

문제

---

제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.

준원이는 대면 수업이 시작되는 바람에 이제 남은 학기의 N일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다. N일간의 두 메뉴는 이미 공지되어 있고, 준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.

준원이는 N일간 학식에 총 X원 이하를 써야 한다.

여러분이 N일간 준원이의 메뉴를 잘 골라서, 고른 메뉴의 맛의 합을 최대화 해주자!

입력

---

첫째 줄에는 두 정수 N, X가 주어진다.

둘째 줄부터 N개의 줄에, 각 날에 먹을 수 있는 5,000원짜리 메뉴의 맛 A와 1,000원짜리 메뉴의 맛 B가 공백을 사이에 두고 주어진다.

 

출력

---

준원이가 고른 메뉴들의 맛의 합을 최대화했을 때의 값을 출력하라.

 

제한

---

•  1 ≤ N ≤ 100000
•  1000N ≤ X ≤ 5000N
•  1 ≤ A ≤ 10,000, 1 ≤ B ≤ 10,000

문제 풀이

---

그리디 + 정렬 문제.

 

쓸 수 있는 최대 금액과 코너 A의 가격, 코너 B의 가격이 고정되어 있으므로 코너 A에서 주문할 수 있는 최대 횟수를 구할 수 있다. 만약 코너 A에서 주문할 수 있는 횟수가 a라면, 5000a + 1000*(N - a) = X로 표현할 수 있다. 따라서 a = (X - N * 1000) / 4000가 된다.

정렬을 이용해서 코너 B보다 코너 A에서 얻을 수 있는 맛이 큰 날짜들을 선택해 코너 A에서 주문할 수 있는 횟수인 a까지 주문하여 전체 맛의 최댓값을 얻어낼 수 있도록 한다. 단, 해당 날짜들에 A를 선택하면 다른 날짜에 B를 선택해야 하므로 무작정 코너 A의 값의 큰 것을 선택하는 것이 아니라 한 날짜의 A와 B의 맛 차이가 큰 날짜들을 선택해서 코너 A에서 주문하면 된다. 또한 예제 3번처럼 코너 A에서 주문할 수 있지만 A보다 B가 큰 경우 코너 A에서 주문할 수 있는 횟수를 모두 채우지 않고 B를 선택해주면 된다.

 

문제 풀이

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

bool cmp(pair<int, int>& p1, pair<int, int>& p2)
{
	int diff1 = p1.first - p1.second;
	int diff2 = p2.first - p2.second;
	if (diff1 > diff2)
	{
		return true;
	}
	else if (diff1 == diff2)
	{
		if (p1.first > p2.first)
		{
			return true;
		}
		else if (p1.first == p2.first)
		{
			return p1.second > p1.second;
		}
		else
		{
			return false;
		}
	}
	else
	{
		return false;
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, X;
	int answer = 0;
	cin >> N>> X;
	pair<int, int>* arr = new pair<int, int>[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].first >> arr[i].second;
	}
	int maxAMenuSelect = (X - N * 1000) / 4000;
	sort(arr, arr + N, cmp);
	for (int i = 0; i < N; i++)
	{
		if (i < maxAMenuSelect)
		{
			if (arr[i].first >= arr[i].second)
			{
				answer += arr[i].first;
			}
			else
			{
				answer += arr[i].second;
			}
		}
		else
		{
			answer += arr[i].second;
		}
	}
	cout << answer << "\n";
	return 0;
}