[C++] 백준 13305번: 주유소

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

13305번: 주유소

오답 풀이

도시 나열의 전체 구간[0, N - 1]에서 기름 단가가 가장 낮은 곳을 찾는다. 그곳의 위치를 K라고 하자.

그 이후 구간[K, N - 1]의 전체 도로의 길이를 구한 뒤, K 도시의 기름 단가를 곱한 값을 ans에 누적한다.

이제, 도시 나열의 남은 구간[0, K - 1]에서 기름 단가가 가장 낮은 곳을 찾는다. 

그리고 위를 K가 0이 될 때까지 반복한다.

이렇게 해서 틀렸다.

https://excited-hyun.tistory.com/71

[백준 13305 - C++] 주유소 : 그리디 알고리즘

위의 풀이를 봤다.

내가 생각했더 풀이처럼 복잡하게 할 필요도 없다.

첫 주유소부터 시작하여 기름값을 계산하면서

이제껏 적용해왔던 기름 단가보다 낮아지면 그거로 갱신하면 된다.

한 번만 순회하면 되므로 시간복잡도는 N이다.

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, N)	for(int i = 0; i < N; ++i)
#define TC(T)		int T; cin >> T; while(T--)
#define FAST_IO		cin.tie(NULL); ios::sync_with_stdio(false);
#define ERR			1e-13
#define EL			"\n"
#define VI			vector<int>
#define VVI			vector<VI>
#define VVVI		vector<VVI>
#define VP			vector<pair<int, int>>
#define VVP			vector<VP>
#define VC			vector<char>
#define VVC			vector<VC>
#define VB			vector<bool>
#define VVB			vector<VB>
#define VVVB		vector<VVB>

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N;
	cin >> N;

	VI roadLengths(N, 0);
	FOR(i, N - 1)
		cin >> roadLengths[i];

	VI oilStations(N);
	FOR(i, N)
		cin >> oilStations[i];

	int oilCost = oilStations[0];
	long long totalCost = (long long)roadLengths[0] * oilCost;
	for (int i = 1; i < N; i++) {
		if (oilStations[i] < oilCost)
			oilCost = oilStations[i];
		totalCost += (long long)roadLengths[i] * oilCost;
	}

	cout << totalCost << EL;

	return 0;
}