[백준] 13305번 : 주유소

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 그리디 알고리즘 문제로, 현재 상황에서 어떤 도시에서 기름을 넣는 것이 더 저렴할지 선택해야 한다.
현재 도시보다 더 저렴한 기름값의 도시가 나오기 전까지는 현재 도시에서 기름을 충전하고, 그 이후에는 더 저렴한 기름값의 도시에서 기름을 충전하는 방식을 반복하면 된다.

1) dis와 price 벡터에 각각 도시 간의 거리와 각 도시의 기름값을 입력받아 저장한다.

2) 현재 위치한 도시와 그 다음 도시의 인덱스를 저장하기 위해 priceA, priceB를 선언하고 0과 1로 초기화한다. 그리고 현재 지나가야할 경로의 인덱스를 저장하기 위해 disIdx를 선언하고 0으로 초기화한다.

3) dis의 길이만큼 반목문을 돌면서

• 가장 먼저 totalPrice에 현재 도시(priceA)의 기름값 * 현재 지나야할 경로(disIdx)의 길이를 더해준다.
• 현재 도시(priceA)의 기름값이 다음 도시(priceB)의 기름값보다 작거나 같을 경우
  : priceA는 유지하고 priceB를 1 증가시킨다.
• 반대로 현재 도시의 기름값이 다음 도시의 기름값보다 클 경우
  : priceA를 priceB로 교체하고, priceB는 교체된 priceB에서 1 증가시킨 값으로 교체해준다.
• 반복문을 한 번 돌 때마다 disIdx를 1 증가시킨다.

4) 반복문이 모두 끝나고 나면 totalPrice를 반환시켜 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

long long solution(vector<long long> distance, vector<long long> price)
{
	long long totalPrice = 0;
	int disIdx = 0, priceA = 0, priceB = 1;

	for (int i = 0; i < distance.size(); i++)
	{
		totalPrice += (price[priceA] * distance[disIdx]);
		if (price[priceA] <= price[priceB])
			priceB++;
		else
		{
			priceA = priceB;
			priceB = priceA + 1;
		}
		disIdx++;
	}
	return totalPrice;
}

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

	int n;
	cin >> n;

	vector<long long> dis;
	vector<long long> price;

	for (int i = 0; i < n - 1; i++)
	{
		long long d;
		cin >> d;
		dis.push_back(d);
	}

	for (int i = 0; i < n; i++)
	{
		long long p;
		cin >> p;
		price.push_back(p);
	}

	cout << solution(dis, price);
}