백준 13305 주유소

www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디 문제다 언제나 그렇듯 O(N)을 반복하며 각 순간의 최적의 선택을 해주어야한다. 이 문제의 경우 조건이 두가지가 존재한다. 하나는 오른쪽 도시로 가는데 최적의 비용이고 거리의 길이만큼 무조건의 기름을 갖고있어야했다. 이 문제를 해결하기 위해서는 기준점이 되는 점의 기름 가격보다 더 적거나 같은 값의 가격이 나올 때 까지 반복문을 돌려 체크해준다. 더 큰 점의 경우에는 지나가며 거리를 저장해..

2021.01.10