BOJ 백준 13305 : 주유소

시작하면서

이번 문제는 그리디 알고리즘(Greedy Algorithm) 카테고리 문제이다.

BOJ 13305 - 주유소

​

문제 이해

​ 이 문제는 가장 적은 양의 기름으로 모든 거리를 가야한다. 도시의 최대 개수가 100,000개이므로 O(N) 이하의 시간 복잡도로 문제를 해결해야하는 것을 유추할 수 있고, 거리와 리터의 최대 값이 1,000,000,000이므로 변수를 잡을 때 overflow를 주의해야 한다.

1. 첫 도시부터 마지막 도시까지 이동하면서 매번 현재 상태의 최소 기름 값을 갱신한다.
2. 갱신된 현재 최소 기름 값으로 다음 도시까지 이동할 수 있을만큼 기름을 넣는다.
3. 1~2를 반복하면서 마지막 도시까지 방문한다.

​

해결

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<unsigned int> distanceBetweenCities;
	int N;

	cin >> N;

	distanceBetweenCities.resize(N - 1);
	for (unsigned int i = 0; i < N - 1; i++)
	{
		cin >> distanceBetweenCities[i];
	}

	unsigned int currentMinimumOilPrice = UINT32_MAX;
	unsigned long long totalOilPrice = 0;
	for (unsigned int i = 0; i < N; i++)
	{
		unsigned int oilPrice;
		cin >> oilPrice;

		if (i == N - 1)
			break;

		if (oilPrice < currentMinimumOilPrice)
		{
			currentMinimumOilPrice = oilPrice;
		}

		totalOilPrice += (unsigned long long)currentMinimumOilPrice * distanceBetweenCities[i];
	}

	cout << totalOilPrice;

	return 0;
}