[백준] C++ 13305번 주유소 실버3 - Greedy Algorithm

문제 : https://www.acmicpc.net/problem/13305
분류 : Greedy Algorithm(그리디 알고리즘)

접근

1. 기름값이 가장 싼 곳에서 많이 기름을 채워야한다.
2. 그 곳을 찾기 전까지는 각 주유소에서 거리만큼만 주유하고 가장 저렴이를 찾으면 그곳에선 남은 거리만큼 주유한다.
3. 제약조건이 있기 때문에 고려를 해야한다.

슈도코드

input 거리 N-1만큼
input 가격 N만큼

최솟값 = 99999

for N
  최소가격 지정
  sum += 최소가격 * 거리

풀이

#include<iostream>
#include<algorithm>
#define MAX 1000000000
using namespace std;

int main()
{
	long long dist[100001];
	long long price[100001];
	long long N, minPrice, sum = 0;
	cin >> N;

	for (int i = 0; i < N-1; i++)
		cin >> dist[i];
	
	for (int i = 0; i < N; i++)
		cin >> price[i];
	
	minPrice = MAX;

	for (int i = 0; i < N; i++) {
		if (price[i] < minPrice)
			minPrice = price[i];
		sum += minPrice * dist[i];
	}

	cout << sum;

}