[백준] 주유소 13305 C++

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

 

해설

그리디 문제이다.

(첨에 문제가 길어서 좀 쫄았는데 쫄지말자)

처음에 좀 고민을 했다. 이거 DP인가 그리디인가??

한 10~15분쯤 고민하니까 딱 명확하게는 아니지만 언제 최소가 되는지 숨겨진 규칙?을 찾아 냈다.

4
2 3 1
5 2 4 1

순으로 입력을 받는다고 했을 때 5 : A, 2 : B, 4 : C, 1 : D라고 하자.

A에서는 딱 2리터만 주유해야하고 B에서는 4리터를 주유해야 최소값이 나온다.

여기서 알 수 있는게 다음 마을의 기름값이 더 싸다면 다음 마을까지 가는 거리 만큼만 주유해야 최소값이 나온다는 것을 알 수 있다.

B에서는 B마을 보다 가격이 싼 주유소가 있는 마을이 나오는 거리만큼 주유를 해야한다는 것을 알 수 있었다.

A에서는 거리 2만큼만 주유하고(다음 마을이 B인데 기름 가격이 더 싸기 때문에) B에서는 4리터를 주유한다. (D마을의 기름 값이 더 싸기 때문)

 

현재 상태에서 '최적'의 선택을 하여 최종결과 또한 '최적'의 결과를 보장하는 그리디라 할 수 있다.

좀더 쉽게 설명하면 그냥 그때 그때 최선의 선택을 해서 최종 결과 또한 최선의 결과가 나오도로 하는 것이다.

 

결과값은 int 로 하면 범위를 초과하니 long long으로 해주는 것도 잊지말자.

 

코드

첫 풀이

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;

#define endl "\n"
#define ll long long
#define R first
#define C second
#define F first
#define S second

// 현재 가격 보다 싼 가격이 나올 때까지 거리를 누적하고 싼 가격이 나오면 현재 값을 더한다.
int n, cost[100004], dist[100004];

int main(void)
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n - 1; ++i) cin >> dist[i];
	for (int i = 0; i < n; ++i) cin >> cost[i];
	ll cur = cost[0], idx = 0, dis = 0, ret = 0;
	for (int i = 1; i < n; ++i)
	{
		// 가격이 더 낮은 주요소를 만난 경우 이때까지 지나온 거리를 누적한다.
		if (cur > cost[i])
		{
			dis += dist[i - 1];
			ret += cur * dis;
			cur = cost[i];
			idx = i;
			dis = 0;
		}
		else
		{
			dis += dist[i - 1];
		}
	}

	if (dis != 0)
		ret += cur * dis;

	cout << ret;
}

 

아래는 좀 코드를 개선한 풀이이다.

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
#include <climits>
#include <limits>
using namespace std;

using ll = long long;
#define endl "\n"
// #define ll long long
#define R first
#define C second
#define F first
#define S second

int n, cost[100004], dist[100004];

int main(void)
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i < n; ++i) cin >> dist[i];
	for (int i = 1; i <= n; ++i) cin >> cost[i];

	int minCost = INT32_MAX;
	ll distSum = 0;
	for (int i = 1; i < n; ++i)
	{
		if (cost[i] < minCost) minCost = cost[i];
		distSum += ll(minCost) * ll(dist[i]);
	}
	cout << distSum;
}