[백준 13305] 주유소 / Node.js / 그리디 알고리즘 기초

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

13305번: 주유소

 

• 문제 지문이 길어도 요점을 이해하는 것이 중요
• 1. 기름값이 저렴한지 비교한다.
• 2. 더 저렴한 주유소까지만 갈 수 있는 기름만 주유하고 이동한다.
• 본 문제에선 단위의 값이 크므로 BigInt를 사용하여야 한다.

 

const input = require('fs').readFileSync('/dev/stdin')
.toString().trim()
.split('\n')
.map((v)=> v.split(' ').map((v) => BigInt(v)))  // BigInt로 자료형 변환

let distance = input[1] // 도시와의 거리
let charges = input[2]  // 도시별 주유소의 요금

let cost = 0n;  // 누적비용을 저장할 변수
let curPrice = charges[0]  // 최저 요금은 초기 주유소의 요금으로 세팅

for(let i=0; i<distance.length; i++){
  cost += curPrice * distance[i]  // 현최저 * 거리 = 비용에 누적
  if(curPrice > charges[i+1]) curPrice = charges[i+1]  // 현요금이 다음 주유소의 요금보다 비쌀경우 요금을 다음 주유소의 요금으로 갱신
}

console.log(String(cost));