주유소

문제

https://www.acmicpc.net/problem/13305

해당 문제는 입력으로 주어진 노드와 간선 정보를 통해 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소 비용을 계산하는 문제이다.
노드는 해당 도시에서의 기름값을 의미하고, 간선은 도시 사이의 거리를 의미한다.

처음에는 기름값이 가장 싼 도시를 찾아서, 이후 거리는 모두 가격이 가장 싼 도시에서 주유한 기름으로 이동하고, 나머지 거리는 매 도시마다 주유를 하여 이동하는 코드를 구성했다.

하지만 만약 전체 10개 도시 중에서, 7번째 도시의 주유소가 가장 싸고, 2번째 도시의 기름값이 2번째로 싸고, 3번째 도시의 기름값이 가장 비싸다면,
내가 구성한 위의 코드는 최소 비용을 만족하지 않는다.

따라서 그리디 알고리즘을 활용하여 위의 코드를 다시 생각하면 다음과 같은 과정을 생각할 수 있다.
1) 매 도시를 순회할 때마다 기름값을 비교하여 기름값이 가장 싼 도시를 min 변수에 저장하고,
2) 매번 두 도시 사이 거리를 min 변수에 저장된 기름값으로 충전하여 이동한다고 생각한다.

위와 같은 과정을 거치면 매 가장 좋은 선택을 한 결과가 가장 최적의 결과를 얻을 수 있게 된다.

그리디 알고리즘을 활용한 해당 스타일의 접근에 충분히 익숙해질 필요가 있다고 생각한다...

※ P. S.
그리고 또한, 해당 문제의 입력 데이터 크기에 유의하여 결과를 저장하는 변수의 자료형에도 유의해야 한다!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);

	long long n, temp, res, min_idx, min = 2147000000, total = 0, else_dist = 0, idx = 0;
	vector<int> dist;
	vector<int> cost;

	cin >> n;

	for (int i = 1; i < n; i++) {
		cin >> temp;
		dist.push_back(temp);
		total += temp;
	}

	for (int i = 0; i < n; i++) {
		cin >> temp;
		cost.push_back(temp);
	}
	
	res = 0;

	for (int i = 0; i < n - 1; i++) {
		if (cost[i] < min) {
			min = cost[i];
		}
		res = res + (min * dist[i]);
	}

	cout << res << "\n";
	return 0;
}