이분탐색1 [백준] 1800번 인터넷 설치 (C++) https://www.acmicpc.net/problem/1800 문제를 보고 다익스트라 알고리즘을 사용해야 하는것은 알겠으나여기서 1번노드 부터 N번 노드까지 확장했을때 최단경로를 구하는 것은 아니였기에 어떤 방법을 사용해서 최소 값을 출력해야하는지 구할 수가 없었다.따라서 다른 사람들 풀이를 보니 이분탐색을 활용하여 간선에 대한 상한선을 지정해 준다 즉 비용이 mid 이하인 간선을 무료로 사용하고이보다 큰 간선은 비용이 든다고 가정했을 때, 총 유료 간선의 개수가 K개 이하로 N번노드에 도달할 수 있는지 판별하는 방법이다. 예를들어 다음 테스트 케이스 1번을 보자 이분탐색을 사용해서 mid 값을 4라고 지정했을때 3번 노드 2번 노드의 누적 거리 값은 0으로 될 것이다.하지만 4번 노드 5번 노드는.. 2025. 6. 26. 이전 1 다음
