[BOJ] C++ 13305: 주유소 - 우선순위 큐와 그리디 알고리즘

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 예제 4 2 3 1 5 2 4 1 ans : 18 4 3 3 4 1 1 1 1 ans : 10 문제를 잘 생각해 보면 기름 값이 가장 싼 도시를 3번 도시라고 하자. 그럼 3번 도시부터 목적지까지의 거리만큼 기름을 3번 도시에서 다 사두고 2번 도시를 다시 목적지로 두고 반복하면 된다. 이렇게 구현한다면 기름 값이 가장 싼 도시를 계속해서 갱신해야 하므로 우선순위 큐를 사용했다. 그리고 목적지를 갱신하는 방법은 좀 번거로워서 방문처리를 하는 방식을 ..

2024.02.16