문제

boj13305_00 boj13305_01

현재까지 지나온 주유소 중 리터당 가격이 가장 저렴한 주유소를 기억하면 된다. 그런데 리터당 가격은 1억 이하이고 도시가 100000개니까 정답의 자료형은 long long을 쓰면 되는데, 도시의 개수는 2 <= N <= 100,000인데 왜 int형 배열을 쓰면 틀리는지? 이것 때문에 세 번 만에 풀었다.

boj13305_1 boj13305_2 boj13305_3 boj13305_4 boj13305_5

구현

#include <iostream>
#define MAX 100001
using namespace std;

long long price[MAX]; // price[i]: i번째 주유소의 리터당 가격
long long dist[MAX]; // dist[i]: i번째 주유소와 i+1번째 주유소 사이의 거리

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, i, min;
	long long sum = 0;
	cin >> N;

	for (i = 0; i < N - 1; i++) cin >> dist[i];
	for (i = 0; i < N; i++) cin >> price[i];

	min = price[0]; // 현재까지 지나온 주유소 중 리터당 가격이 가장 저렴한 주유소
	sum = 0;

	for (i = 1; i < N; i++) {
		if (price[i - 1] < min) min = price[i - 1];
		sum += min * dist[i - 1];
	}

	cout << sum << endl;
	return 0;
}