Problem Solving/BOJ
백준 13305번 주유소 - C++ 풀이
어멘드
2022. 9. 27. 17:14
반응형
1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다.
1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다.
기름통의 크기가 무제한이므로, 그리디하게 각 도시에 도착하기 전에 가장 싼 주유소에서 기름을 넣고 오면 최적이다. 일반화하면, i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 주유소에서 넣고 오면 된다. 이때 i-1번 도시에서 i번 도시까지의 거리를 dist[i], 1~(i-1)번 도시 중 가장 싼 주유소의 가격을 min_price[i]라고 하면 비용은 dist[i] * min_price[i]이다.
반응형
#include <iostream>
using namespace std;
typedef long long ll;
int N;
ll dist[100001], price[100001], min_price[100001];
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];
for (int i=0; i<N; i++) cin >> price[i];
min_price[0] = price[0];
for (int i=1; i<N; i++) {
min_price[i] = min(price[i], min_price[i-1]);
}
// 가장 싼 곳에서 넣고 온다
ll ans = 0;
for (int i=0; i<N-1; i++) ans += dist[i] * min_price[i];
cout << ans;
return 0;
}
반응형