https://www.acmicpc.net/problem/14464
14464번: 소가 길을 건너간 이유 4
첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다.
www.acmicpc.net
그리디 문제다.
풀이
소와 닭의 이동시간을 비교해서 조건이 맞는 경우를 세는 문제다. 단, 여기서 중요한 점은 소의 이동가능시간이다. 해당 부분의 정렬 조건에 대해 생각하는 데에 오랜 시간이 걸렸다.
닭 i가 소 A와 소 B 두 마리 모두 데려다줄 수 있는 경우, 둘 중 이동 가능 시간의 범위가 더 좁은 경우를 우선적으로 선택해야 선택받지 못한 소를 다음 순번의 닭이 데려다줄 가능성이 더 높아지게 된다. 즉 닭의 시간을 오름차순 정렬, 소의 이동시간이 짧은 순서 & 움직이기 시작한 시간이 오름차순으로 정렬이 되어야 한다는 이야기다.
소의 움직임이 완료된 시간을 기준으로 오름차순, 움직임이 완료된 시간이 같다면 움직이기 시작한 시간 기준으로 오름차순으로 정렬한 뒤, 오름차순으로 정렬된 닭의 시간을 기준으로 데려갈 수 있는 소들을 탐색하여 접근하였다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [3048] 개미 (0) | 2023.02.04 |
|---|---|
| [14466] 소가 길을 건너간 이유 6 (0) | 2023.02.03 |
| [1544] 사이클 단어 (0) | 2023.01.30 |
| [1263] 시간 관리 (0) | 2023.01.29 |
| [2607] 비슷한 단어 (2) | 2023.01.27 |