[백준 15589] Lifeguards (Silver)
문제 www.acmicpc.net/problem/15589 알고리즘 Sweeping 풀이 $N$명의 라이프가드가 있습니다. 한 명을 해고했을 때, 가장 긴 시간을 커버하도록 해야 합니다. 다른 사람과 근무시간이 겹치지 않는 시간을 고유 시간이라고 정의하겠습니다. 해고하지 말아야할 사람은 고유시간이 큰 사람들입니다. 자신의 가치가 높다는 뜻입니다. 반대로 해고해야할 사람은 고유시간이 가장 작은 사람입니다. 사람마다의 고유시간을 구할 수 있다면 이 문제에서 푼 것과 같이 $N$명의 총 근무시간에서 고유시간이 가장 짧은 사람을 해고하면 될 일입니다. 첫 번째 단계로 모든 사람의 총 근무시간을 구해봅시다. #include #define rep(i, n) for (int i = 0; i < n; ++i) #def..
Algorithm
2021. 2. 5. 14:09
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- bfs
- 세그먼트트리
- 정렬
- 펜윅트리
- kmp
- implementation
- sorting
- 좌표압축
- 이분매칭
- 이분탐색
- sweeping
- spring
- Oracle
- spring boot
- hld
- greedy
- knapsack
- SCC
- 2-SAT
- 트라이
- Fenwick
- 스위핑
- Segment tree
- dfs
- DP
- string
- Suffix Array
- dijkstra
- 동적계획법
- union find
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함