(cpp) Baekjoon 13305번 문제 ‘주유소’ - 그리디 알고리즘

03 Jan 2023 on Programming Languages

Baekjoon 13305번 문제 ‘주유소’ - 그리디 알고리즘

---

문제

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<deque>
#include<algorithm>
using namespace std;
deque<long long int> dlist;
deque<long long int> plist;
int n; //도시 갯수
int dis; //거리 입력받기
int price; //가격 입력받기

int main() {
	cin >> n;
	int ret1 = n-1;
	int ret2 = n;
	while (ret1--) {
		cin >> dis;
		dlist.push_back(dis);
	}
	while (ret2--) {
		cin >> price;
		plist.push_back(price);
	}
	long long int result=0;
	long long int dist = dlist.front(); 
	long long int lowest = plist.front(); //초기최저값
	for (int i = 1; i < n - 1; i++) {
		if (plist[i] < lowest) {
			result += lowest * dist; //10
			lowest = plist[i]; //2
			dlist.pop_front();
			dist = dlist.front();
		}
		else {
			dlist.pop_front();
			dist += dlist.front();
		}
	}
	result += lowest * dist;
	cout << result;
}