https://www.acmicpc.net/problem/19623
회의는 한번에 하나만 진행이 가능하며, 주어지는 N개의 회의들을 적절하게 배정하여 최대 인원을 구하는 문제입니다.
저는 dp + parametric search로 접근했습니다.
dp[N]: N번째 회의부터 모을 수 있는 최대 인원
우선 회의들을 시작시간 기준 오름차순으로 정렬합니다.
그리고 해당 회의를 진행하거나, 진행하지 않거나 두가지를 모두 확인할 수 있습니다.
이번 회의를 넘긴다면 바로 idx + 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
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 100001
using namespace std;
typedef struct Node {
int l, r, s;
}Node;
Node list[MAX];
int dp[MAX];
int N;
bool cmp(Node a, Node b) {
return a.l < b.l;
}
int bs(int x) {
int l = 0;
int r = N;
while (l < r) {
int m = (l + r) >> 1;
if (list[m].l >= x) r = m;
else l = m + 1;
}
return l;
}
int solve(int idx) {
if (idx >= N) return 0;
int& ret = dp[idx];
if (ret != -1) return ret;
return ret = max(solve(idx + 1), list[idx].s + solve(bs(list[idx].r)));
}
void func() {
sort(list, list + N, cmp);
memset(dp, -1, sizeof(dp));
cout << solve(0) << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i].l >> list[i].r >> list[i].s;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 30461 낚시 (0) | 2024.07.28 |
|---|---|
| boj 17258 인기가 넘쳐흘러 (0) | 2024.07.20 |
| boj 1398 동전 문제 (0) | 2024.07.04 |
| boj 1229 육각수 (0) | 2024.06.30 |
| boj 25378 조약돌 (0) | 2024.06.29 |