https://www.acmicpc.net/problem/23559
A 메뉴를 선택할 수 있다면 선택하는 것이 좋습니다.
하지만 보유중인 금액은 한계가 있으므로 최적의 선택을 하기 위해 A, B 메뉴 맛의 차이가 큰 것을 선택하는 것이 좋습니다.
그래서 A - B를 기준으로 내림차순 정렬해줍니다.
그다음 0원으로 시작하여 A를 선택하게 되면 나중에 금액이 부족해질 수 있습니다.
따라서 시작 금액을 모든 메뉴를 B로 선택하는 N * 1000으로 세팅할 수 있습니다.
그렇게 한다면 A 메뉴를 선택했을 때 4000원만 추가해주면 되고, 금액이 부족해지면 추가금액 없이 B를 선택해줄 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
typedef pair<int, int> pii;
pii list[MAX];
int N, X;
bool cmp(pii a, pii b) {
return a.first - a.second > b.first - b.second;
}
void func() {
sort(list, list + N, cmp);
int ret = 0;
int cost = N * 1000;
for (int i = 0; i < N; i++) {
if (cost + 4000 <= X && list[i].first > list[i].second) {
cost += 4000;
ret += list[i].first;
}
else ret += list[i].second;
}
cout << ret << '\n';
}
void input() {
cin >> N >> X;
for (int i = 0; i < N; i++) {
cin >> list[i].first >> list[i].second;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 15553 난로 (0) | 2024.07.13 |
|---|---|
| boj 1437 수 분해 (0) | 2024.07.12 |
| boj 2140 지뢰찾기 (0) | 2024.07.10 |
| boj 1132 합 (0) | 2024.07.08 |
| boj 25381 ABBC (0) | 2024.07.07 |