[c++/백준] 13305번: 주유소

문제 링크

13305번: 주유소

풀이

그리디를 이용하는 문제

1. 한 도시를 갈 때마다 오름차순 정렬되는 우선순위 큐에 기름값을 넣는다.
2. 현재 갱신된 기름 값 중 제일 작은 값(pq.top())에 다음 도시까지의 거리를 곱해 answer에 더해준다.
3. 맨 마지막 도시까지 갱신하면 끝.

answer 범위는 long long인거 알았는데, int*int가 자동으로 형변환 될 줄 알았는데 안되네..
dist랑 cost 모두 long long 형으로 바꿔주니 성공했다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main(void)
{
	int n;
	cin >> n;

	vector<long long> dist(n-1);
	vector<long long> cost(n);
	for (int i = 0; i < n-1; i++)
	{
		cin >> dist[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> cost[i];
	}

	long long answer = 0;
	priority_queue<long long, vector<long long>, greater<long long>> pq;
	for (int i = 0; i < n-1; i++)
	{
		pq.push(cost[i]);
		answer += pq.top()*dist[i];
	}

	cout << answer << endl;

	return 0;
}