[백준 13305] 주유소 with Node.js

문제 링크

www.acmicpc.net/problem/13305

13305번: 주유소

풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const n = +input[0];
const distance = input[1].split(" ").map(v => BigInt(v));
const price = input[2].split(" ").map(v => BigInt(v));

let curPrice = price[0];
let cost = 0n;

for (let i=0; i<n-1; i++) {
    cost += curPrice * distance[i];
    if (curPrice > price[i+1]) curPrice = price[i+1];
}

console.log(String(cost));

일단 n의 최댓값이 10⁵, 거리와 가격은 10⁹로 매우 크므로, BigInt를 사용하였다.

 

최소 비용을 구하는 방법은 다음과 같다.

1. 현재 위치한 주유소보다 기름값이 더 저렴한 가장 가까운 주유소를 오른쪽에서 찾는다.

2. 더 저렴한 주유소까지만 딱 갈 수 있는 연료를 현재 위치한 주유소에서 주유하고 그 주유소까지 간다.

3. 이 과정을 반복한다.

 

위 과정은 반복문에서 (현재 위치에서 다음 주유소로 가는 거리) X (현재 주유소의 기름값)을 매번 비용에 누적시키고, 다음 주유소의 기름값이 더 저렴할 경우, 현재 주유소의 기름값을 다음 주유소의 기름값으로 갱신함으로서 구현할 수 있다.