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

문제

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

 

문제 내용

n개의 도시가 일직선으로 놓여있다.

2번째 줄에는 도시 간의 거리가 주어지고, 마지막 줄에는 각 도시별 주유소의 리터당 가격이 주어진다.

우리는 가장 왼쪽 도시에서 가장 오른쪽 도시로 가기 위한 최소 비용을 구하면 된다. 

 

 

문제 풀이

입력받은 가격의 배열에서, 무조건 수가 작아질 때를 사용하는 것이 답이다.

즉, 지나가면서 최솟값을 계속 갱신해두고 가면 최소 비용을 얻을 수 있다.

위 설명에서 알 수 있듯이, 이 문제는 greedy 하게 풀 수 있다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

	//입력
	int n;
	cin >> n;
	vector<int>km(n - 1);
	vector<int>won(n);

	for (int i = 0; i < n - 1; i++) cin >> km[i];
	for (int i = 0; i < n; i++) cin >> won[i];

	//문제 해결
	//long long이 아니라 int로 하면 부분점수만 얻는다.
	long long money = won[0];
	long long ans = 0;
	for (int i = 0; i < n-1; i++) {
		money = min(money,(long long) won[i]);
		ans += km[i] * money;
	}

	//결과 출력
	cout << ans << '\n';
}

 

문제 코드 설명

입력 조건을 보면, 거리와 가격이 모두 1 이상 1,000,000,000 이하의 자연수로 주어진다.

만약 거리와 가격이 모두 1,000,000,000이라면 int의 범위를 한참 벗어나기 때문에 long long 자료형을 사용했다.