[BOJ] 13305 주유소 - 그리디 알고리즘.

매우 간단한 문제이다.

배열을 순회하며 도시를 지날때마다 요금을 정산하는 식으로 한다.

우선 바로 이전 도시에서 해당 도시까지 달린 요금을 정산한다.

 

물론 저장된 최저기름값으로 한다.

이러면 기름값이 가장 싼 도시에서 미리 주유한것과 같다.

 

해당 도시의 기름값이 더 싸다면

최저기름값을 업데이트하고, 

다음도시로 향하면 된다.

 

#include <iostream>

int NumOfCity = 0;
unsigned long long GasPrice				[100001] = { 0 , };
unsigned long long DistanceToNextCity	[100001] = { 0 , };


int main()
{
	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);

	std::cin.tie(0);
	std::cout.tie(0);

	std::cin >> NumOfCity;

	for (int i = 1; i < NumOfCity; ++i)
		std::cin >> DistanceToNextCity[i];

	for (int i = 1; i <= NumOfCity; ++i)
		std::cin >> GasPrice[i];

	unsigned long long Ans = 0;
	unsigned long long LowestPrice = 0x7fffffffffffffff;

	unsigned long long TempDistance = 0;
	
	GasPrice[NumOfCity] = 0;

	for (int i = 1; i <= NumOfCity; ++i)
	{
		TempDistance += DistanceToNextCity[i - 1];

		if (LowestPrice > GasPrice[i])
		{
			Ans += TempDistance * LowestPrice;
			LowestPrice = GasPrice[i];
			TempDistance = 0;
		}
			
	}

	std::cout << Ans << '\n';
	return 0;


}