[c/c++] 백준 13305 (Silver 3)

🔨 문제

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

<요약>
n개의 도시를 입력받고 n-1개의 km, n개의 주유소의 리터당 가격을 입력

자동차를 타고 왼쪽에서 오른쪽으로 n개의 주유소를 지나칠 때 최소의 비용으로 운행하는 총 금액을 구하는 것

🔨 해결방법

1. 어떻게 하면 최소비용?

n개의 주유소를 지나치는데 주유소마다 가격이 제각각이다.
하지만 이전의 주유소보다 더 저렴한 가격의 주유소가 나온다면 그 주요소에서 충전하는 것이 낫다.

예를 들어 주유소 4개가 있는데 리터당 가격이 각각 5-2-4-1 이라고 하고, 그 사이의 km는 각각 2-3-1이라고 하면 (5*2)+(2*4)로 충전해서 가는 것이 낫다. 두 번째 주유소가 리터당 2원이기 때문

그래서 맨 처음의 주유소를 min으로 정하고, min보다 더 적은 주유소가 나타나면 min값을 변경하는 식으로 코드를 구성했다.
나는 더 적은 min값이 나올 때까지 km를 쭉 더해주고 변경 전 min값에 곱하고 total_fee 변수에 저장해줬다.
(하지만 꼭 total_fee를 사용할 필요는 없다. 계속 곱해주면서(min*kilometer[i-1]) i 값을 높여도 되기 때문)

하지만 나는 또 실수한 부분이 있었는데, 너무 작은 값이 나오는 부분에만 집착한 나머지 주유소가 5-4-6처럼 끝 부분이 최솟값이 나오지 않을 수 있다는 점을 간과했다.

하지만 이 모든 것을 고쳐도 나는 맞왜틀을 했는데,,,,
보니까 내가 배열의 크기를 잘못 설정했더라,,,,,,,.,...,... 흗흗흑극......
0을 하나 빼먹었다

🔨 코드

#include <iostream>
using namespace std;

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

	int n;
	cin >> n;
	int kilometer[100000] = { 0 };
	int gasStation[100000] = { 0 };
	long long total_fee = 0;
	for (int i = 0; i < n - 1; i++) {
		cin >> kilometer[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> gasStation[i];
	}

	int min = gasStation[0];
	long long total_K = 0;
	for (int i = 1; i < n; i++) {

		total_K += kilometer[i-1];	// 기존의 주유소보다 저렴한 주요소가 있을 때까지 더함

		if (gasStation[i] <= min) {	//  더 저렴한 주유소가 나왔을 경우	
			total_fee += total_K * min;	// 여태까지 더한 거리와 주유소 최솟값 곱함
			min = gasStation[i];	// min값 변경
			total_K = 0;	// 비우기
		}
		if (i == (n - 1)) {	// 주유소가 5 4 6 처럼 min값보다 더 큰 값이 나올 수 있기 때문에 조건식 적용 
			total_fee += total_K * min;
		}		
	}
	cout << total_fee;
	
	return 0;
}