[백준] 6209_제자리 멀리뛰기 (Javascript)

문제

BOJ6209_제자리 멀리뛰기

풀이

이 문제는 이진 탐색으로 푸는 문제다.
이진 탐색으로 어떻게 접근할 수 있을까?

1. 시작 지점부터 시작 지점까지의 거리(0)을 left로 두고 목적지 까지의 거리(d)를 right로 한다.

2. left와 right의 중간을 mid로 한다. 이때의 mid를 학생들이 한번 뛸 때의 최소 거리라고 생각하면 된다.
   (예를 들어 d=25일 경우 mid의 초깃값은 12((0+25)/2)이고, 학생들은 한번 뛸 때 최소 12이상의 거리는 뛰어야 한다는 뜻이다.)

3. mid를 설정해주었으면 모든 돌섬의 거리를 탐색한다.
   돌섬의 개수(n)가 총 5개고 제거할 수 있는 돌섬의 개수(m)은 2개, 시작 지점으로부터의 거리는 각각 [2, 11, 14, 17, 21] 라고 가정하고, 여기에 추가로 목표 지점(d)까지의 거리도 추가해주면 [2, 11, 14, 17, 21, 25] 가 된다.
   (입력값으로 주어지는 돌섬의 거리는 정렬되지 않은 채로 주어지기 때문에 오름차순으로 미리 정렬을 해두어야 한다.)

4. 학생들은 최소 12 이상은 뛰어야 하기 때문에 0->14 이렇게 섬을 한 번 밖에 밟고 갈수밖에 없으므로 섬을 밟은 횟수cnt는 1이다. 하지만 학생들은 n-m+1(도착지점)개 이상의 돌섬을 밟아야 하기 때문에 이에 맞게 mid를 조정해주어야 한다.

5. cnt < n-m+1 인 경우에는 점프 거리를 작게 만들어서 더 많은 섬을 밟아야 하기 때문에 right = mid-1 로 두어 mid값을 작게 만들고, cnt >= n-m+1 일때는 그때의 mid 를 answer에 저장해두고 최소 거리를 키울 수 있는 경우가 더 있을 수 있있는지 확인하기 위해 left = mid+1로 두어 mid값을 크게 만든다.

6. 2번~5번 과정을 계속해서 반복해주다가 left가 right보다 커지면 반복을 종료시키고 answer에 저장된 값을 출력해주면 된다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [d, n, m] = input[0].split(' ').map(Number);
const stones = input.slice(1).map(Number);
stones.push(d);
stones.sort((a, b) => a - b);

let answer = 0;
let left = 0;
let right = d;
while (left <= right) {
    let mid = (left + right) >> 1;
    let preStone = 0;
    let cnt = 0;
    for (let stone of stones) {
        if (stone - preStone >= mid) {
            cnt++;
            preStone = stone;
        }
    }
    if (cnt >= n - m + 1) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

console.log(answer);

후기

처음엔 각각의 돌섬에 번호를 매긴 뒤 돌섬을 정점으로 하고 모든 돌섬을 간선으로 이어서 N-M번 만에 목적지까지 도착하는 경로를 찾았으면 경로를 잇는 간선의 비용(거리)의 차이를 계산해서 그때의 최솟값을 갱신하는 방법으로 접근을 하였으나 모든 정점을 잇기 위해선 $\frac{n(n-1)}{2}$ 번의 연산을 수행해야 하므로 이는 $O(n^2)$이므로 시간 초과가 날것 같았다.

다른 접근법을 떠올려보려고 했지만 떠오르지 않아 다른 분의 코드를 보고 풀었다.

참고

https://welog.tistory.com/206