BOJ - 13305 주유소

문제 링크 : https://www.acmicpc.net/problem/13305

문제 유형 : 그리디 알고리즘

문제 티어 : 실버3

문제 풀이 : 주유소의 기름 가격과 도로의 길이가 나와 있다. 최소 비용을 구하려면 당연히 가격이 싼 주유소에서 제일 많이 넣어야 한다. 많이 넣어야 한다는 것은 다음 거리로 갈 때까지 최대한 많이 넣어야 한다는 점이다. 즉, 다음 도시 주유소 가격이 지금 주유소보다 싸면 다음 주유소 가격으로 설정해주고 그렇지 않다면 지금 최저가의 주유소 가격을 기본 값으로 계속 유지해줘야 한다. 그 후 거리를 곱해주면 최소 비용이 나올 것이다.

 

1) 첫 번째 주유소의 가격을 minValue로 설정해줌.

2) 그 후 도시들을 순회하면서 기름 가격이 비싼 지 현재 minValue와 다음 도시들의 값들과 비교한다.

3) 만약 minValue보다 다음 도시들의 값이 더 싸면 바꿔주고 그렇지 않으면 유지해준다.

4) 고로 minValue를 최솟값으로 유지한 채 각 도시까지 가는 거리를 곱해서 미리 주유를 해준다.

5) 가격 출력해준다. 

 

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);
let distance = input[1].split(" ").map(Number);
let oilPrice = input[2].split(" ").map(Number);
let minValue = Number.MAX_SAFE_INTEGER; // JS에서 나타낼 수 있는 가장 큰 숫자
let total = BigInt(0);
for (let i = 0; i < N - 1; i++) {
    if (oilPrice[i] < minValue) {
        minValue = oilPrice[i];
    }
    total += BigInt(minValue) * BigInt(distance[i]);
}
console.log(total.toString()); // BigInt로 처리한 큰 수이기 때문에 문자열로 변환해주는게 안전함