[백준알고리즘] 13305번: 주유소 -C++

[백준알고리즘] 13305번: 주유소 -C++

13305번: 주유소 (acmicpc.net)

13305번: 주유소

처음에 메모이제이션을 사용한 방법을 사용해 각 도시에서 끝 도시까지의 최단 거리를 계산하는 방법을 사용했다. 이러한 방법은 시간 초과가 났다. 다시 생각해보니까 도시의 개수를 고려하니 시간이 훨씬 초과될만했다.

 

그래서 새로운 방법을 생각했고, 그리디한 방법으로 접근하면 된다는 것을 알게 됐다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제를 풀 때 그리디한 방법으로 접근해 해결할 수 있었다. 바로 현재 기름값보다 적은 기름값의 도시가 나올 때까지 갈 수 있는 기름을 넣는 방법이다. 그리고 현재보다 더 적은 기름값을 갖는 도시에서 새로 기름을 채우는 방법이다.

 

이러한 방법을 사용하게 되면 굳이 각각의 도시마다 최종 목적지까지의 최소 가격을 구할 필요가 없다.

 

생각해보면 현재보다 비싼 도시에서 기름을 채우면 더 손해인건 확실하니까 현재보다 더 적은 도시까지만 이동하고, 거기서 새로 기름을 채우는 것이 최소 가격인 것이다.

 

이렇게 접근법을 바꾸게 되니 문제를 푼 코드도 더욱 간결해졌다.

 

아래의 C++ 코드 중 마지막에 최종 가격을 계산하는 과정에서 minimumCost += ((int64_t)currentOilPrice * road[i]);부분이 있다. 여기서 (int64_t)로 형 변환을 시켜주지 않는다면 int형끼리의 곱셈 연산으로 오버플로우가 발생한다. 이 부분만 조심하면 문제를 쉽게 해결할 수 있다.

#include <iostream>
#include <vector>
#include <climits>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

void solve(void)
{
	int countCity;
	std::cin >> countCity;

	std::vector<int> road(countCity - 1);
	for (int i = 0; i < countCity - 1; i++)
		std::cin >> road[i];

	std::vector<int> priceOil(countCity);
	for (int i = 0; i < countCity; i++)
		std::cin >> priceOil[i];

	int64_t minimumCost = 0;
	int currentOilPrice = INT_MAX;
	for (int i = 0; i < countCity - 1; i++)
	{
		currentOilPrice = priceOil[i] < currentOilPrice ? priceOil[i] : currentOilPrice;
		minimumCost += ((int64_t)currentOilPrice * road[i]);
	}

	std::cout << minimumCost;
}