백준 1800 파이썬1 1800. 인터넷 설치 (Python) 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 풀이 이분탐색과 다익스트라를 결합하여 해결하는 문제다. 과정은 다음과 같다. 1. 먼저 이분탐색을 통해 기준이 되는 가격을 설정한다. 2. 그 후 다익스트라를 통해서 1번과 N번을 연결한다. 3. 이 때, 기존에는 dist 배열에 시작 지점부터 해당 지점까지의 최단 거리를 넣어줬는데 이번 문제에서는 기준 가격을 넘는 케이블을 몇 개 사용했는지를 담는다. 4. 마지막에 dist[N]의 값이 공짜로 제공되는 케이블선의 개수인.. 2022. 4. 4. 이전 1 다음
