Algorithm/Greedy
[Greedy] 백준 13305번 "주유소" C++ 풀이
운호(Noah)
2022. 2. 14. 17:51
문제 링크
풀이
예제 그림
문제는, 현재 도시의 주유 가격이 다음 도시의 주유 가격보다 비싼지, 저렴한지에 따라 나뉘게 됩니다.
현재 주유소보다 다음 주유소가 싸다면,
현재 주유소에서는, 다음 주유소로 이동하는 데에 걸리는 거리만큼만 주유하고, 다음 주유소에서 더 주유하는 것이 이득입니다.
만약, 현재 주유소가 다음 주유소보다 싸다면,
다음 주유소에서 다다음 주유소까지 이동하는 데에 걸리는 거리만큼, 현재 주유소에서 더 주유하는 것이 이득입니다.
즉, 도시를 이동할 때마다 기름을 채워주되,
이전에 등장했던 주유 가격 중 가장 최소의 가격으로 기름을 채울지, 현재 주유소의 가격으로 기름을 채울지만 정하면 됩니다.
주의 사항
- 첫 번째 도시에서 두 번째 도시로 이동할 경우, 어떤 경우이던지 간에, 첫 번째 도시에서 주유해야합니다.
- 마지막 지점의 기름값은 무시해도 됩니다.
- 도시간 거리와 도시별 기름값의 범위는 1 ~ 1,000,000,000 이므로, 각각 long long 타입을 사용해야합니다.
- 결과값 또는 함수 반환 타입도 잘 확인해서 long long 형으로 맞춰줘야합니다.
코드
#include <iostream>
#include <vector>
using namespace std;
// 도시 별 도로의 길이
vector<long long> road;
// 도시 별 주유 가격
vector<long long> oil;
// 최소 누적 비용
long long total_oil_cost;
// 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는, 최소 비용 계산
long long greedy(){
// 우선, 첫 번째 도시의 주유 비용을 최소 주유 비용으로 지정
long long min_oil_cost = oil[0];
// 첫 번째 도시에서 두 번째 도시로 갈때에는, 반드시 첫 번째 도시에서 주유
// 따라서, 두 번째 도시까지는 주유를 마친 상태
total_oil_cost += oil[0] * road[0];
// 두 번째 도시부터 제일 오른쪽 도시까지, 도시 별 주유 가격을 확인
for (int i=1; i<oil.size()-1; ++i){
// i 번째 도시의 주유 가격이, 현재까지의 최소 주유 비용보다 비싸다면,
if (oil[i] > min_oil_cost){
// 현재까지의 최소 주유 비용으로, i+1 번째 도시까지 이동할 수 있도록 주유
total_oil_cost += min_oil_cost * road[i] ;
}
// i 번째 도시의 주유 가격이, 현재까지의 최소 주유 비용보다 싸다면,
else{
// i 번째 도시의 주유 가격을, 최소 주유 비용으로 변경한 뒤,
min_oil_cost = oil[i];
// 최소 주유 비용으로, i+1 번째 도시까지 이동할 수 있도록 주유
total_oil_cost += min_oil_cost * road[i] ;
}
}
// 최소 누적 비용 반환
return total_oil_cost;
}
int main(){
// 도시 개수
int n;
cin >> n;
// 도시 별 도로의 길이
for (int i=0; i<n-1; ++i){
long long road_len;
cin >> road_len;
road.push_back(road_len);
}
// 도시 별 주유 가격
for (int i=0; i<n; ++i){
long long oil_cost;
cin >> oil_cost;
oil.push_back(oil_cost);
}
// 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용 계산
cout << greedy() << endl;
}