[Baekjoon] 13305번: 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

 

---

 

문제 해결 과정

착안

아래와 같이 탐욕(greedy) 알고리즘에 기반하여 문제를 해결할 수 있다.

 

• 현재 위치해 있는 도시의 주유 비용을 기준으로 삼는다.
• 순차적으로 우측 도시를 탐색하며 현재 도시의 주유 비용보다 주유 비용이 더 저렴한 도시를 탐색한다.
• 탐색에 성공하면, 현재 도시에서 주유하여 해당 도시까지 한 번에 이동한다.
• 탐색에 실패하면, 현재 도시에서 마지막 도시까지 한 번에 이동한다.
• 위의 과정을 가장 우측 도시에 도착할 때까지 반복한다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int N;
int Cities[100000];
int Edges[99999];
size_t Cost;

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

	cin >> N;
	for (int i = 0; i < N - 1; i++)
		cin >> Edges[i];

	for (int i = 0; i < N; i++)
		cin >> Cities[i];

	int i = 0;
	while (i < N - 1)
	{
		int oilCost = Cities[i];
		int distSum = 0;

		while (oilCost <= Cities[i])
		{
			if (i == N - 1)
				break;

			distSum += Edges[i++];
		}

		Cost += (size_t)distSum * (size_t)oilCost;
	}

	cout << Cost << "\n";
	return 0;
}

 

실행 결과