문제
일직선 도로 위에 N개 도시가 있다. 각 도시의 주유소 리터당 가격과 도시 간 거리가 주어질 때, 제일 왼쪽 도시에서 제일 오른쪽 도시까지 이동하는 최소 비용을 구하라.
핵심 포인트
- Greedy: 현재까지 만난 주유소 중 가장 싼 곳의 가격으로 기름을 넣으면 된다.
- 더 싼 주유소를 만나기 전까지는 이전 최저가로 필요한 만큼만 넣는다.
- 마지막 도시의 기름 가격은 의미 없다 (목적지이므로).
C++ 풀이
#include <iostream>
using namespace std;
int N, min_oil, city, minimum;
int dist[100001];
long long result;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N - 1; i++) cin >> dist[i];
cin >> min_oil; // 첫 번째 도시의 기름값
result = (long long)min_oil * dist[0]; // 첫 구간은 반드시 여기서 넣어야 함
for (int i = 1; i < N - 1; i++) {
cin >> city;
min_oil = min(min_oil, city); // 최저가 갱신
result += (long long)dist[i] * min_oil; // 최저가로 다음 구간 이동
}
cout << result;
return 0;
}
풀이 흐름
- 첫 번째 도시에서는 선택지가 없다. 여기서 기름을 넣고 출발해야 한다.
- 두 번째 도시부터는 현재 도시의 기름값과 지금까지의 최저가를 비교한다.
- 더 싸면 최저가를 갱신한다. 어차피 이전 구간은 이미 지나왔으므로, 앞으로의 구간만 최저가로 계산하면 된다.
- 각 구간의 거리 × 최저가를 누적하면 답이다.
왜 Greedy가 성립하는가
직선 도로이므로 되돌아갈 수 없다. 한번 지나친 싼 주유소는 다시 이용할 수 없다. 따라서 “지금까지 본 것 중 가장 싼 가격”으로 기름을 넣는 것이 항상 최적이다. 만약 앞에 더 싼 주유소가 있다면, 거기서부터는 그 가격으로 갱신될 것이다.
주의사항
오버플로우: 거리와 가격이 모두 최대 10⁹이므로 곱하면 int 범위를 초과한다. 결과를 long long으로 선언해야 한다.
복잡도
- 시간: O(N) — 한 번 순회
- 공간: O(N) — 거리 배열
왼쪽에서 오른쪽으로 한 번만 훑으면서 최저가를 갱신하는 것이 전부다. Greedy의 핵심은 “되돌릴 수 없는 선택 구조”에서 성립한다.
댓글