BOJ 3683 - 고양이와 개
싫어하는 것에 대하여 충돌이 일어나는 사람을 향하는 간선을 추가해주면 된다. 이분매칭을 진행하고 v - max가 답이다.
BOJ 1202 - 보석 도둑
무게가 가벼운 보석부터 보면 된다. 우선순위 큐를 이용하여 C_i보다 가벼운 보석들 중에 가장 비싼걸 가져가면 된다.
BOJ 9006 - 다리
먼저 좌표 순으로 정렬한다. 그리고 왼쪽 다리는 m, 오른쪽 다리는 n의 가중치를 두고 nm에서 가중치를 빼다가 양수가 아니게 될 때가 답이 된다.
BOJ 9484 - 최대삼각형, 최소삼각형
Rotating Sweep Line Technique 기초문제이다. 두 점을 잇는 선분을 기준으로 왼쪽과 오른쪽에서 각각 먼 점과 가까운 점을 뽑고 넓이를 계산하면 된다. O(N²lgN)
'백준 문제풀이' 카테고리의 다른 글
| 5/24 PS (3) | 2022.05.25 |
|---|---|
| 5/23 PS (2) | 2022.05.23 |
| 백준 13159 - 배열 [Python] (0) | 2022.05.02 |
| 백준 10227 - 삶의 질 [Python] (0) | 2022.04.29 |
| 백준 20669 - Close to You [Python] (0) | 2022.04.24 |