https://www.acmicpc.net/problem/1263
문제를 보자마자 6068번 시간 관리하기 문제랑 같다는 것을 느꼈습니다.
마감 시간(Si)과 일을 하는데 걸리는 시간(Ti)이 주어지고, 언제부터 시작하면 일을 끝낼 수 있는지 구해야 합니다.
마감 시간 기준 내림차순으로 정렬하여 뒤에서부터 탐색한다면 쉽게 해결할 수 있습니다.
저는 혹시 몰라서 Si가 같다면 Ti 기준으로도 정렬을 했지만 생각해보니 그럴 필요는 없어보입니다.
시간을 최대로 세팅을 먼저 하고, 내려가면서 Ti를 빼주시면 되겠습니다.
도중에 현재 작업의 Si보다 t가 더 크다면 Si로 현재 시간을 조정해주시면서 진행해주시면 됩니다.
|
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
45
46
47
|
#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
typedef pair<int, int> pii;
pii list[MAX];
int N;
bool cmp(pii a, pii b) {
if (a.second == b.second) return a.first < b.first;
return a.second > b.second;
}
void func() {
sort(list, list + N, cmp);
int t = 1e9;
for (int i = 0; i < N; i++) {
t = min(t, list[i].second);
t -= list[i].first;
if (t < 0) {
cout << "-1\n";
return;
}
}
cout << t << '\n';
}
void input() {
cin >> N;
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 28325 호숫가의 개미굴 (0) | 2024.07.06 |
|---|---|
| boj 14464 소가 길을 건너간 이유 4 (0) | 2024.07.05 |
| boj 18185 라면 사기 (Small) (0) | 2024.07.02 |
| boj 16120 PPAP (0) | 2021.10.16 |
| boj 2262 토너먼트 만들기 (0) | 2021.10.16 |