[백준] 13305. 주유소 (자바스크립트/javascript/js/node.js/그리디 알고리즘/탐욕법)

 

 

문제를 풀기 위한 아이디어

문제가 장황하지만, 결국 생각해야할 포인트는 단순하다.

가장 최저가인 곳에서 기름을 구매해서 제일 오른쪽 도시(도착점)까지 가면 되는데, 그 최저가인 지점까지 도착하기 전까지는 그 전에 있는 곳 중 최저가에서 구매를 해야 한다. 이게 계속 반복된다.

생각을 조금 전환시키면, 매 순간 순간마다 최저가를 갱신시키면 된다. 현재 최저가가 지금 머무르고 있는 곳의 가격보다 비싸다면 최저가가 갱신되는 것이다. 그렇게 해서 최저가와 갈 거리를 곱해서 총 비용에 누적시키면 된다.

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let input = fs.readFileSync("예제.txt").toString().split("\n");
let cost = BigInt(0);
const N = Number(input[0]); // N: 도시의 개수
const distance = input[1]
  .trim()
  .split(" ")
  .map((element) => BigInt(element)); // distance: 각 도시 사이의 도로 길이

let city = input[2]
  .trim()
  .split(" ")
  .map((element) => BigInt(element)); // city : 도시마다 주유소의 리터당 가격

let lowestPrice = city[0]; // 처음에는 맨 처음 값을 최저가를 지정
for (let i = 0; i < city.length - 1; i++) {
  if (lowestPrice > city[i]) {
    //  현재 값이 최저가보다 작다면 최저가를 갱신해준다.
    lowestPrice = city[i];
  }
  cost += lowestPrice * distance[i];
}
console.log(cost.toString());

수가 엄청 큰 값이 주어지기 때문에 이전에 10757. 큰 수 A+B에서 다룬 것 처럼 BigInt형을 사용한다. BigInt형을 사용할 때에는 문자열로 출력을 해주어야 한다.

BigInt에 대한 부분은 아래를 참고하세요.

 

[백준] 10757. 큰 수 A+B

[백준] 10757. 큰 수 A+B (자바스크립트/node.js/javascript/알고리즘/코딩테스트)