글 읽기 - Parallel Binary Search 관련해서..

안녕하세요 지금 머그컵 문제를 풀어보고 있는데요!

머그컵 문제 중에 놀이기구인가 놀이동산인가 그 문제를 풀고 있는데

아무리 알고리즘을 생각해도 Time Complexity가 O(QK)가 나와서 어쩌지 이러다가 풀이를 봤어요

Parallel Binary Search를 쓰면 된다구 하더라구요...

근데 이 부분에 대해서 한글로 정확히 설명되어 있는 곳도 없고... 영어로 배우자니 뭔 소리인지 잘 모르겠고..ㅠㅠ 혹시 이 부분을 자세히 설명하고 있는 사이트 없을까요? ㅠㅠ

그리고 Parallel Binary Search를 사용하지 않고 해결할 수 있는 방법도 있을까요?ㅠㅠ

감사합니다

저는 O(Q (log N)^2)으로 풀었습니다.

쿼리마다 이진탐색을 통해 두 아이가 처음으로 놀이기구를 탈 수 있을 때를 구할 수 있으면 됩니다.

우선 조금 더 생각해보시고 모르면 질문하셔도 됩니다. 이것말고도 풀이가 더 있을 수도 있습니다.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge