백준 13305번 : 주유소

그리디 개념 : 미래를 생각하지 않고 각 단계에서 최선의 선택을 했을 때 전체적으로도 최선이 되는 경우에 사용

 

문제 링크 : www.acmicpc.net/problem/13305

내 풀이(2021.1.6.) :

#include <iostream>

using namespace std;

long long dist[100000 - 1];
long long cost[100000];

int min_index;
long long min_cost = 1000000000;

long long total_cost = 0;
long long remaining_dist = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;
	for (int i = 0; i < N - 1; i++) {
		cin >> dist[i];
		remaining_dist += dist[i];
	}

	for (int i = 0; i < N; i++) {
		cin >> cost[i];
	}

	for (int i = N - 2; i >= 0; i--) {
		if (min_cost > cost[i]) {
			min_cost = cost[i];
			min_index = i;
		}
	}

	for (int i = 0; i < min_index; i++) {
		total_cost += cost[i] * dist[i];
		remaining_dist -= dist[i];
	}

	total_cost += cost[min_index] * remaining_dist;

	cout << total_cost;
	
	return 0;
}

결과 : 틀렸습니다

반례 : www.acmicpc.net/board/view/60029

5
3 2 1 4
5 8 9 4 1

output : 56
answer : 46

 

알고리즘 자체를 잘못 짰다.

 

내 풀이2(2021.1.6.) :

#include <iostream>

using namespace std;

long long dist[100000 - 1];
long long cost[100000];
long long min_cost = 1000000000;
long long total_cost = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		cin >> dist[i];
	}

	for (int i = 0; i < N - 1; i++) {
		cin >> cost[i];
		if (min_cost > cost[i]) min_cost = cost[i];
		total_cost += min_cost * dist[i];
	}

	cout << total_cost;

	return 0;
}

결과 : 성공