https://www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
그리디는 많이 안풀어봐서 어렵네요..
이 문제는 정렬 + 그리디 문제입니다.
우선 마감일, 과제 점수를 담은 list배열을
- 과제 점수가 높은 순 (내림차순)
- 마감일이 적게 남은 순 (오름차순)
으로 정렬합니다.
그 다음 과제 점수가 가장 높은 0번 인덱스부터 과제를 진행합니다.
여기서 확인해야할 것은 마감일 안에 과제를 할 수 있는지에 대한 여부입니다.
d일부터 1일까지 visit[d]=true인지 확인해서 해당 일에 과제를 했는지 체크합니다.
과제를 했다면 전날 과제를 했는지 체크하는 방식으로 1일까지 확인합니다.
과제를 하지않은 날이 있다면 과제를 진행하고 방문체크 해주면 되고,
d ~ 1일 모두 이미 과제를 한 상태면 해당 과제를 진행할 수 없다는 뜻입니다.
|
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
48
|
#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;
typedef pair<int, int> pi;
pi list[MAX];
bool visit[MAX + 1];
int N;
bool cmp(pi a, pi b) {
if (a.second == b.second) return a.first < b.first;
else return a.second > b.second;
}
void func() {
int ans = 0;
for (int i = 0; i < N; i++) {
int d = list[i].first;
for (int j = d; j > 0; j--) {
if (visit[j]) continue;
visit[j] = true;
ans += list[i].second;
break;
}
}
cout << ans << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i].first >> list[i].second;
}
sort(list, list + N, cmp);
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 16120 PPAP (0) | 2021.10.16 |
|---|---|
| boj 2262 토너먼트 만들기 (0) | 2021.10.16 |
| boj 1826 연료 채우기 (0) | 2021.02.22 |
| boj 8980 택배 (0) | 2021.02.16 |
| boj 11000 강의실 배정 (0) | 2021.02.16 |