허비의 기술블로그

문제 설명 N개의 도시가 일직선으로 연결돼있고, 각 도시에는 주유소가 있다. 연결된 도시의 거리 배열, 각 도시의 기름값 정보 배열이 들어올 때 최소의 비용으로 첫 번째 도시에서 마지막 도시까지 가는 비용을 구하는 문제다. (단, 기름을 실을 수 있는 양은 무한대이며, 기름값과 거리는 10억 이하의 자연수이다. 또한 도시의 개수는 최대 10만 개다.) 시간 복잡도 : O(N) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 방법 도시를 차례로 지나가며 소모한 기름 값을 계산할 때, 각각 현재..