[백준 C++] 13305 주유소 - 그리디

13305번: 주유소

#include <iostream>
#include <vector>
using namespace std;

vector<pair<long long, long long>> City;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	City.reserve(N);

	for (int i = 0; i < N; ++i)
	{
		int Distance = 0;
		if (i < N - 1)
		{
			cin >> Distance;
		}
		City.emplace_back(0, Distance);
	}

	for (pair<long long, long long>& Info : City)
	{
		long long Cost;
		cin >> Cost;
		Info.first = Cost;
	}

	long long Cost = 0;
	int NextStation = 0;
	for (int i = 0; i < N - 1; ++i)
	{
		if (i != NextStation)
		{
			continue;
		}

		long long CurCost = City[i].first;

		NextStation = i + 1;
		while (CurCost < City[NextStation].first)
		{
			++NextStation;
		}

		for (int j = i; j < NextStation; ++j)
		{
			Cost += CurCost * City[j].second;
		}
	}

	cout << Cost;
}

---

 

현재 노드의 비용이 뒤의 노드보다 적게 드는지 반복적으로 비교해서

더 적은 비용이 드는 노드의 이전 노드 까지의 모든 거리를 현재 노드의 비용으로 커버하는 방식으로 풀었습니다.