[백준] 13305 - BigInt 사용하기

const fs = require('fs');
const filePath = process.platform === 'linux' ? 'dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

//도시 마다 가야 되는 거리가 적혀있고
//도시마다 기름값이 적혀있음
//처음에는 첫 도시에서 기름을 넣어주고 다음 도시로 이동
//다음 도시로 이동할 때 기름값이 더 싸면 그 도시에서 기름을 넣어주고 다음 도시로 이동
//기름값이 더 비싸면 다음 도시로 이동
//도착지로 이동할 때 필요한 최소비용을 구하라

let N = parseInt(input[0]);
let distance = input[1].split(' ').map((i) => BigInt(i));
let cost = input[2].split(' ').map((i) => BigInt(i));

let result = 0n;

let minCost = cost[0];

for (let i = 0; i < N - 1; i++) {
  if (minCost > cost[i]) {
    minCost = cost[i];
  }
  result += minCost * distance[i];
}

console.log(String(result));

최근에 취업 준비를 위해 꾸준히 알고리즘 문제 풀이를 하고 있습니다. 문제를 풀고 나서 어떻게 풀었는 지 주석으로 기록을 해두려고 하는데 자꾸 기억이 날아가버려서 정리를 못하게 되는 것 같아, 블로그 글로 남기면서 기억도 하려고 합니다. 

위의 문제는 그리디 문제 목록 중에 13305 주유소 문제 입니다. 

처음에 문제에 대해서 접근 할 때는 전체를 돌면서 비교를 해줘야 될까, 정렬이 필요한 문제일까를 고민 하다가, 앞에서 부터 뒤로 쭉 for문으로 넘어가면서 만약 이전에 기름값이 더 싸다면 이전 장소에서 미리 넣고 오면 되겠구나 라고 생각을 했습니다. 생각보다 단순하게 최소값을 두고 계속해서 기름 값을 갱신 해주는 식으로 풀어주면 되었습니다. 

오히려 문제 풀이 과정에서 포인트는 JavaScript로 문제를 푼다는 점이었습니다. JavaScript로 알고리즘 문제를 풀다큰 수를 다뤄야 하는 경우가 자주 있습니다. 특히 문제에서 입력값이 10억(1,000,000,000)까지 허용되는 경우, 단순한 곱셈 연산이더라도 JavaScript의 Number 타입의 안전한 정수 범위를 초과할 수 있어 BigInt 사용이 필수적입니다.

일반적으로 JavaScript의 Number 타입은 9007199254740991(2^53 - 1)까지의 정수만 안전하게 표현할 수 있습니다. 하지만 위의 문제처럼 최대 거리가 10억이고 최대 가격이 10억인 경우, 두 수를 곱하면 10^18이라는 매우 큰 수가 나오게 됩니다. 이는 JavaScript의 Number 타입이 안전하게 표현할 수 있는 범위인 약 9×10^15를 훨씬 초과하는 값입니다.

예를 들어, 일반적인 숫자 타입으로 1000000000 * 1000000000을 계산하면 부정확한 결과가 나오지만, BigInt를 사용하면 정확한 계산이 가능합니다. BigInt는 숫자 뒤에 n을 붙이거나 BigInt() 함수를 사용해 선언할 수 있으며, 이를 통해 JavaScript의 Number 타입 한계를 넘어서는 정수 연산을 정확하게 수행할 수 있습니다.

실제 코드에서는 총 비용을 계산할 때 누적되는 값이 BigInt여야 하며, 거리와 가격을 곱할 때도 모두 BigInt로 변환하여 계산해야 합니다. 결과를 출력할 때는 toString() 메서드를 사용하여 일반 문자열로 변환하면 됩니다. 이러한 BigInt의 활용은 금융 계산이나 큰 수를 다루는 알고리즘 문제에서 정확성을 보장하는 핵심 요소가 됩니다.