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

 

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

 

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

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

---

 

해결전략

 

Greedy Algorithm 탐욕 알고리즘

 

---

 

코드

 

#include <iostream>
#include <vector>
using namespace std;
 
int n, tmp;
long long minCost;
vector<int> r;
vector<long long> c;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n;
	r.resize(n-1);
	for (int i = 0; i < n - 1; i++) {
		cin >> r[i];
	}
	c.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
 
 
	for(int i = 0; i < n; i++)
	{
		tmp = n-1;
		//가스 값이 더 싼 도시 찾기
		for(int j=i; j < n; j++){
			if(c[i] > c[j]){
				tmp = j;
				break;
			}
		}
 
		//다음 도시까지의 길이
		long long nextCity = 0;
		for (int k = i; k < tmp; k++) {
			nextCity += r[k];
		}
		
 
		//다음 도시까지 필요한 가스를 충전. 현재 도시 가스가격 * 다음 도시까지의 길이
		minCost += c[i] * nextCity;
 
		if (tmp < n - 1)
			i = (tmp - 1);
		else
			i = n - 1;
	}
 
	cout << minCost;
 
	return 0;
}

 

 

---

 

 

더 간단한 풀이

 

https://www.acmicpc.net/source/64197315#points

 

로그인

 

www.acmicpc.net