목록이분 탐색 (1)

dh_0e

[PS] 세미나 배정 / C++ (백준 28305번)

2023 UCPC 예선 K번 문제로, 처음엔 그리디 + 우선순위 큐를 사용하여 시도해 봤지만, 큐가 정렬이 되는 기준을 잡는 것이 힘들었을뿐더러, $a_{i}$값이 중복되는 경우에 항상 답을 도출한다는 보장이 없었다. 해결 방법 답으로 출력될 세미나 수의 최솟값($c$)에 대하여 이분 탐색으로 접근해서 bst 함수에서 그리디하게 $i$번째 세미나의 시작 시간을 정한다. 이때 로직은 $c$가 답으로 도출될 수 있게끔 세미나의 시작 시간을 최대한 빠르게 지정한다 (물론 $a_{i}$가 속하게끔). 이후 모든 세미나의 범위에 $a_{i}$가 속하는지 확인하여 true or false를 반환한다. 반환한 값을 바탕으로 이분 탐색이 끝나면 세미나 수의 최솟값을 구할 수 있으며 이분 탐색 + 그리디로 $O(nlog..
알고리즘/Baekjoon 2024. 8. 19. 21:09
이전 Prev 1 Next 다음