백준 23559번: 밥

 

풀이

  준원이가 5000원 메뉴를 골라도, 1000원 메뉴를 고르더라도 일단 N일 동안 1000 * N 원만큼의 최소 비용은 반드시 사용해야만 한다. 먼저 입력받은 (A, B) 값을 구조체 배열에 저장하고, A 값을 기준으로 배열을 내림차순 정렬해주었다. 그 다음에 배열의 인덱스 0부터 1000 * N 이라는 최소 비용에 4000원(5000 - 1000)을 더해가면서 X 원을 넘기지 않을 때까지 A 값을 더해준다. X 원을 초과해야 되면 그 때부터 B 값을 더하면 된다. 

  딴 말이지만 제주대 학점교류로 승마 교양 듣고 싶다 ..🙃

코드

#include <iostream>
#include <algorithm>

#define MAX 100020
using namespace std;

typedef struct {
	int a;
	int b;
} menu;

bool compare(menu m1, menu m2) {
	if (m1.a - m1.b > m2.a - m2.b) {
		return true;
	}

	return false;
}

int N, X, cost = 0, sum = 0;
menu menus[MAX];

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	cin >> N >> X;
	for (int i = 0; i < N; i++) {
		cin >> menus[i].a >> menus[i].b;
	}

	sort(menus, menus + N, compare);

	cost = 1000 * N;
	for (int i = 0; i < N; i++) {
		if ((X >= cost + 4000) && (menus[i].a > menus[i].b)) {
			cost += 4000;
			sum += menus[i].a;
		}
		else sum += menus[i].b;
	}
	
	cout << sum;

}