[백준/BOJ] 13305번 주유소 (C++)

www.acmicpc.net/problem/13305

13305번: 주유소

그리디 유형의 문제입니다.

왼쪽에서 오른쪽 순서대로 도로를 건너갈 때, 현재 비용이 가장 작은 곳의 값에 각 도시를 연결하는 도로의 길이를 곱한 값을 더해주면 되는 문제입니다. 이를 위해 최소힙을 사용하였고, 한 가지 주의할 점은 문제에서 비용과 길이의 입력값이 굉장히 크므로, 더해지는 과정에서 int의 범위를 벗어나는 것을 방지하기 위해 long long으로 선언해줬습니다.

 

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
	int n;
	cin>>n;
	
	vector<long long> distance(n);
	priority_queue<long long, vector<long long>, greater<long long> > cost; // 최소힙 
	
	for(int i = 0; i < n - 1; i++) {
		cin>>distance[i];
	}
	
	long long answer = 0; 
	for(int i = 0; i < n; i++) {
		long long x;
		cin>>x;
		cost.push(x);
		answer += cost.top() * distance[i];
	}

	cout<<answer;
}