4주차(그리디) - [C++]백준13305 주유소

26 Mar 2022 in Study on Algorithm

백준13305 주유소 링크

문제

예제 입력

---

코드

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

vector<int> arr;
vector<int> dist;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	int num;
	for (int i = 0; i < n - 1; i++) {
		cin >> num;
		dist.push_back(num);
	}
	for (int i = 0; i < n; i++) {
		cin >> num;
		arr.push_back(num);
	}

	long long sum = 0;
	long long min = 1000000000;
	for (int i = 0; i < n - 1; i++) {
		if (min > arr[i])
			min = arr[i];
		sum += min * dist[i];
	}
	cout << sum;
}

설명

이 문제는 시작 도시부터 도착 도시까지 여러 도시를 경유하는데 그때마다 주유를 할 수 있어서 1km당 주유비를 측정하는데 최소의 비용을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 각 도시의 주유 비용과 거리를 입력 받아 측정하는데 처음에 있던 곳이 가장 싼 가격이면 채워놓고 가면 되니 min으로 현재 상황마다 최선의 값을 선택하여 측정합니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과