[백준/C++] 13305번 : 주유소 (그리디 문제)

주유소 

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다. 

서브태스크

번호	배점	제한
1	17	모든 주유소의 리터당 가격은 1원이다.
2	41	2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다.
3	42	원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1

4
2 3 1
5 2 4 1

예제 출력 1

18

예제 입력 2

4
3 3 4
1 1 1 1

예제 출력 2

10

---

해당 문제는 그리디 알고리즘을 이용하여 주유소의 기름 비용이 더 작은 주유소를 선택하여 최소의 주유비를 사용해야 하는 문제이다.

❌ 초반에 틀린 풀이법

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N;
	cin >> N;
	vector<int> bridge(N - 1);
	for (int& b : bridge)
		cin >> b;

	vector<int> oilPrice(N);
	for (int& o : oilPrice)
		cin >> o;

	long long result = 0;
	for(int i = 1; i < N; i++)
	{
		if(oilPrice[i-1] >= oilPrice[i]) // 다음 주유소가 더 싸면
		{
			result += (oilPrice[i-1] * bridge[i - 1]);
		}
		else // 현재 주유소가 다음 주유소보다 더 싸면
		{
			result += (oilPrice[i - 1] * (bridge[i - 1] + bridge[i]));
			i++;
		}
	}
	cout << result;
	return 0;
}

문제를 읽고 초반에는 현재 주유소와, 다음 주유소의 가격을 비교해서, 다음 주유소가 더 싸면 현재 주유소에서는 다음 주유소까지의 거리 기름만 충전한다.

만약, 현재 주유소가 다음 주유소보다 더 싸면 그 다음 주유소까지 가는 거리의 기름을 더 충전한다.

 

이런 방식으로 문제를 풀었을 때, 서브태스크 1번만 충족하여 17점이라는 결과가 떴다.

⭕ 맞은 풀이법

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N;
	cin >> N;
	vector<int> bridge(N - 1);
	for (int& b : bridge)
		cin >> b;

	vector<int> oilPrice(N);
	for (int& o : oilPrice)
		cin >> o;

	long long result = 0;
	long long minPrice = 1000000000;
	for(int i = 0; i < N-1; i++)
	{
		if (oilPrice[i] < minPrice)
			minPrice = oilPrice[i];
		result += minPrice * bridge[i];
	}
	cout << result;
	return 0;
}

 

문제의 풀이 방법은 아래와 같다.

 

1. 내가 위치한 주유소의 기름 가격과, 다음 주유소의 기름 가격을 비교하여 더 작은 주유소의 기름 가격을 저장한다.

2. 도로의 개수 (N-1) 만큼 for문을 돌면서 도로의 거리 * 최소 기름 가격을 곱한 결과를 result 에 저장한다.

이때, 문제의 최대 거리, 기름 가격이 10억이기 때문에 long long 자료형으로 결과값을 저장해야 한다.

 

문제의 해결 방법은 매우 간단했지만, 해당 풀이를 생각해내기까지는 매우 오래 걸렸다..

그리디 문제는 항상 이런 것 같다. 풀고나면 간단하지만 풀이방법을 생각해내기까지 너무 오래걸리는 ㅜㅜ 그리디가 제일 어려운 것 같다..

---

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

13305번: 주유소