[백준] 3079 입국심사 (Javascript)

문제

BOJ3079_입국심사

접근법

입력으로 주어지는 변수의 범위가 너무 커서 DP나 이분탐색일 거라고 생각은 했지만 문제에 어떻게 접목시킬지 떠오르지 않았다.

그래서 다른 분의 풀이를 참고했다.

// 모든 사람이 심사를 받는데 걸리는 최소 시간
// N = 입국 심사대 개수, M = 사람 수, T = 심사대별 걸리는 시간
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const T = input.slice(1).map(Number);

// 최소 시간 = 1 (Tk가 1초인 입국심사대가 있고, 사람이 한 명밖에 없을 경우)
// 최대 시간 = 가장 오래걸리는 시간 * 사람 수 (입국 심사대가 한 개밖에 없으면서 시간은 최대한 오래걸리고, 사람은 최대한 많을 때)

T.sort((a, b) => a - b);
let min = BigInt(1); // 최소 시간
let max = BigInt(T[N - 1] * M); // 최대 시간
let answer = max;

while (min <= max) {
    let cnt = BigInt(0);
    let mid = BigInt((max + min) / 2n); // 중간 시간
    T.forEach((time) => {
        // mid시간에 받을 수 있는 인원수
        cnt += mid / BigInt(time);
    });
    if (cnt >= M) {
        answer = answer < mid ? answer : mid;
        // mid시간에 받을 수 있는 인원수가 M보다 크다면 시간을 더 줄여도 됨
        max = mid - 1n;
    } else {
        // mid시간에 받을 수 있는 인원수가 M보다 적다면 시간을 더 늘려야 됨
        min = mid + 1n;
    }
}

console.log(String(answer));

로직 설명

우선 가장 빨리 끝나는 경우의 시간과 가장 늦게 끝나는 경우의 시간을 최소 시간(min)과 최대 시간(max)으로 둔다.

가장 빨리 끝나는 경우는 T$_k$가 1초인 입국 심사대가 있고 사람이 한 명 밖에 없을 경우, 1초만에 입국심사가 끝나는 경우다.

가장 늦게 끝나는 경우는 입국 심사대가 하나밖에 없고, 사람은 최대한 많을 때다. 따라서 가장 오래 걸리는 입국 심사대의 시간과 사람 수를 곱하면 최대 시간을 구할 수 있다.

그리고 $(max+min) \div 2$로 중간 시간(mid)를 구한다.
만약 중간 시간(mid)을 각각의 입국 심사대의 시간(T$_k$)으로 나눈 몫을 구하면 mid시간이 주어졌을 때 몇 명(cnt)의 입국 심사를 마칠 수 있는 지 구할 수 있다.

T.forEach((time) => {
  cnt += mid / BigInt(time);
});

예를 들어 입력이 아래와 같이 주어졌다고 가정해보자.

2 6
7
10

그럼 min, max, mid는 각각 아래와 같이 초기화될 것이다.

min = 1
max = 60
mid = 30

그리고 mid를 각각의 입국 심사대의 시간으로 나눴을 때 몫을 구해보자

30 / 7 = 4
30 / 10 = 3
cnt = 4+3 = 7

그리고 cnt값과 전체 인원수(M)의 대소관계를 비교한다.
만약 cnt가 전체 인원수(M)보다 크거나 같을 경우 시간 여유가 있거나 시간이 딱 맞는 것이므로 max를 mid-1로 줄여주면 된다. 그럼 max의 값이 작아지므로 다음 차례에서 mid의 값은 줄어들게 될 것이다.
그리고 최소 시간을 mid로 갱신해준다.

현재 mid = 30, cnt = 7이므로, 30초에 7명의 입국심사를 끝낼 수 있다는 의미다. 그리고 M=6이므로 시간을 더 줄여도 된다.

만약 cnt < M 인 경우에는 전체 인원의 입국 심사를 완료할 수 없는 것이므로 시간을 늘려줘야 한다. 따라서 min을 mid+1로 늘려줘야 한다.

BigInt를 사용하는 이유

자바스크립트의 원시타입인 Number의 표현 범위는 -2$^{53}$+1 ~ 2$^{53}$-1 까지기 때문이다. 이는 약 10$^{16}$이고, 이를 벗어나는 범위의 계산을 수행할 경우 계산이 수행되지 않는다.

해당 문제에서 최대 시간을 초기화 하기 위해 가장 시간이 오래 걸리는 T$_k$와 인원 수를 곱한 값을 사용하는데, T$_k$와 M이 각각 최대 10$^9$이기 때문에 둘을 곱하면 10$^{18}$이 된다. 따라서 BIgInt를 사용해야 한다.

만약 BigInt를 사용하지 않고 아래와 같이 작성한다면 무한 루프에 빠질수도 있다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const T = input.slice(1).map(Number);

T.sort((a, b) => a - b);
let min = 1; // 최소 시간
let max = T[N - 1] * M; // 최대 시간
let answer = max;

while (min <= max) {
    let cnt = 0;
    let mid = Math.floor((max + min) / 2); // 중간 시간
    T.forEach((time) => {
        cnt += Math.floor(mid / time);
    });
    if (cnt >= M) {
        answer = answer < mid ? answer : mid;
        max = mid - 1;
    } else {
        min = mid + 1;
    }
}

console.log(String(answer));

아래의 입력값으로 실행시키면 무한 루프가 진행된다.

2 1000000000
1000000000
1000000000

어떤 이유로 무한루프가 발생하는 이유를 알고자 디버깅을 진행해봤다.

결론은

min = 499999999999999940
max = 500000000000000000

일때 (max+min)/2를 수행하면 mid = 500000000000000000이 된다.
이때 cnt = 1000000000 = 10^9이 되고, cnt === M이기 때문에 max = mid - 1 이 되어야 한다. 하지만 mid가 Number의 범위를 초과했기 때문에 -1이 적용 되지 않아 max = 500000000000000000이 된다. 따라서 무한 루프가 발생하는 것이고 이를 방지하기 위해 BigInt를 사용한 것이다.