- 문제 링크
백준 13305번 - 주유소
해결 전략
알고리즘 문제를 풀 때는 "최대한 복잡하지 않게 생각해보기"가 매우 중요하다. 아무리 어려운(예를 들어 백준에서 다이아몬드 티어) 문제라도 그 아이디어를 떠올리는 것은 어려울지 몰라도 아이디어의 구현 과정 자체는 결코 난잡하지 않은 경우가 대다수이다(물론, 아닌 경우도 간혹 있지만).
본 문제 역시 마찬가지이다. 문제의 설명을 읽으면 바로 드는 생각이, 본 문제는 Greedy Algorithm으로 해결할 수 있을 것이란 생각이다. 중요한 것은, 너무 복잡한 Greedy를 생각하지 말아야 한다는 것이다. 그러기 위해선 다음의 행위가 중요하다.
문제 상황에 숨겨진 원리나 조건을 찾아보자.
본 문제가 바로 이러한 생각으로 쉽게 풀 수 있다. 참고로 본인은 실제 해결책보다 복잡한 Greedy를 떠올렸고, 결국 최초 시도에서 실패했다.
문제 상황을 이해해보면, 다음과 같은 숨겨진 조건을 찾을 수 있다.
"최소 주유비를 위해선, 매 주유소를 지날때마다 가장 싼 주유비를 택해야 한다."
그말은 즉슨, 주유소 A, B, C가 일렬로 있고, 주유비가 A > C > B인 상황이라 해보자.
1) A에서 출발하자. 최초 주유소는 A이므로 A의 주유비만큼 내고 거리를 이동한다.
2) B에 도달한다. 만약 B의 주유비가 A보다 싸면 B에서 주유하는 것이 당연히 바람직하다.
3) C에 도달한다. C주유비보다 B주유비가 더 싸므로 굳이 주유하지 말고 더 나아가자.
그렇다. "현재 도달한 주유소의 주유비보다 과거에 지나온 주유소의 주유비가 더 싸면 굳이 현재 주유소에서 주유할 필요가 전혀 없다."
이를 인지하면, 문제 풀이는 매우 쉬워진다. 간단한 선형 Traverse로 해결이 가능하다. 구체적인 구현은 굳이 설명이 필요없다. 아래는 코드이다.
#include <iostream>
#include <climits>
// BOJ - 13305 Gas Station
using namespace std;
int cost[100001], dist[100001];
long long solve(int n) {
int MINcost = INT_MAX;
long long dist_sum = 0;
for (int i = 1; i < n; i++) {
if (cost[i] < MINcost) MINcost = cost[i];
dist_sum += (long long)MINcost * (long long)dist[i];
}
return dist_sum;
}
int main(void) {
int n;
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 1; i < n; i++) cin >> dist[i];
for (int i = 1; i <= n; i++) cin >> cost[i];
cout << solve(n);
return 0;
}Greedy를 설계할 때, 문제를 매우 간단하게 바꿀 수 있는 숨겨진 조건이 있는지를 잘 찾아보는 습관을 가지자.
