[문제] https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net [풀이] 해결방법을 찾지 못해, 참고한 문제이다.. 이분탐색 + 다익스트라 방식으로 해결하는 문제이다. 문제에서 제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다. 라는 조건이 있다. 가격으로 들어올 수 있는 최고 금액은 1000000이다. 이분탐색과 다익스트라를 이용하여, 1~1000000까지 중에 최단거리이면서도, 가장 적은 가격을 지불하는..
[문제] https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net [풀이] 기존의 다익스트라 문제의 최소 비용을 저장해두는 배열에, 추가적으로 경로를 저장하는 배열을 사용한다. 최소 비용을 저장해두는 배열을 arr이라고 했을 때, 아래의 경우는 arr을 새롭게 갱신하는 경우이다. 이때 arr을 갱신하면서 경로추적을 위한 배열 route의 idx를 갱신해준다. if(nextWei < arr[nextIdx]) { arr[ne..
https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [풀이] 다익스트라로 풀었다. [코드] import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.PriorityQueue var N = 0 var M = 0 lateinit var map : ArrayList..
문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두..
