1868번 - 보물찾기
그리디하게 연결된 방 수가 많은 곳에서 질문을 던지는게 이득이라고 생각해서 연결된 방 수가 많은 곳부터 방문하고 방문한 후에는 간선들을 끊어줍니다. 간선이 남아있는 곳을 전부 방문하면 종료합니다.
풀어보지는 않았지만, 이런 간단한 아이디어로 풀리는 문제였다면 루비5가 아닐 것 같습니다.
이 글을 참고해 보세요
https://www.secmem.org/blog/20...
참고로 저 위의 링크 글 이해 못 합니다.
문제를 잘못 이해하신거 같네요.
트리가 일자 모양일 때는
일반적인 배열에서의 binary search와 동치이기 때문에
정답은 log n 이 나와야합니다.
지금 코드는 n/2 비슷한 무언가가 나오겠네요
댓글을 작성하려면 로그인해야 합니다.
p_ce1052 3년 전
그리디하게 연결된 방 수가 많은 곳에서 질문을 던지는게 이득이라고 생각해서 연결된 방 수가 많은 곳부터 방문하고 방문한 후에는 간선들을 끊어줍니다. 간선이 남아있는 곳을 전부 방문하면 종료합니다.