[C/C++] 백준 13305, Greedy

문제

13305번: 주유소 (acmicpc.net)

13305번: 주유소

코드

#include <vector>
#include <iostream>

using namespace std;

int main() {
	vector<long> dis(100001, 0);
	long N, temp, price = 1000000000, result = 0;
    cin >> N;
	for (int i = 0; i < N-1; i++)
		cin >> dis[i];
	
    for (int i = 0; i < N; i++) {
		cin >> temp;
		if (temp < price)
			price = temp;
		result += price * dis[i];
	}
	cout << result;
}

풀이

1. 각 도시 사이의 거리를 벡터 dis에 저장한다. 기본 수치가 큰 문제이므로 변수들을 long 타입으로 초기화한다.

(*빠른 저장을 위해 dis의 크기를 N의 최댓값으로 미리 설정한 후 모든 값을 0으로 설정했음)

2. 휘발유 가격을 저장하는 변수에는 미리 휘발유의 최댓값을 저장한다.

3. 휘발유 가격을 입력받으며 기존의 휘발유 가격과 비교한 후, 기존 가격보다 저렴하면 휘발유 가격을 재설정한다.

4. result에 휘발유 비용(가격*다음 도시까지의 거리)을 더한다.