1446 지름길

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

=====

문제 분석

지름길의 정보들을 start 와 end로 정렬한다. 이때  end가 도착지점인 d를 초과한다면 쓸모 없으므로 filter했다.

const infos = input
    .slice(1)
    .map((s) => s.split(' ').map(Number))
    .filter((v) => v[1] <= d)
    .sort((a, b) => {
        if (a[0] === b[0]) {
            if (a[1] === b[1]) {
                return a[2] - b[2];
            }
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });

출발점부터 d까지 이동할 때 지름길을 사용하거나 사용하지 않는 경우들이 있다.

이것에 대해 모든 경우의 수를 구해본다 => n이 12이하이기 때문에 경우의 수는 최대 4095개로 굉장히 작다.

const combinations = [];
const makeCombinations = (arr) => {
    if (arr.at(-1) >= infos.length - 1) return;
    let start = arr.at(-1) + 1 || 0;
    for (let i = start; i < infos.length; i++) {
        if (arr.includes(i)) continue;
        combinations.push([...arr, i]);
        makeCombinations([...arr, i]);
    }
};

이제 위에서 구한 조합들을 모두 탐색해보면서 최종적인 코스트 중 가장 작은 값을 출력하면 된다.

조합에서 구한 정보를 통해 코스트를 계산할 때 주의할 점은 현재의 위치가 다음 지름길보다 더 멀리 와 있는 경우 쓸모 없는 경우이므로 그 정보는 버려야 한다는 것이다. 예를 들어 그 전 지름길이 10->50 이면서 비용이 1 들어서 50에 왔는데 다음으로 온 지름길 정보가 10->50 이고 비용이 10이면 이것은 쓸모없는 루트이기 때문이다. 여기에서 이 루트를 버렸더라도 이 비용이 10드는 지름길을 사용하지 않는 루트는 조합 배열에 이미 포함되었기 때문에 break때려도 상관없다.

let answer = d;

for (const combi of combinations) {
    let current = 0;
    let sumCost = 0;
    for (const idx of combi) {
        const [start, end, cost] = infos[idx];
        if (current > start) break
        if (start > current) {
            sumCost += start - current;
        }

        sumCost += cost;
        current = end;
    }
    if (current < d) {
        sumCost += d - current;
    }
    answer = Math.min(answer, sumCost);
}

console.log(answer);

정답 코드

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

const [n, d] = input[0].split(' ').map(Number);
const infos = input
    .slice(1)
    .map((s) => s.split(' ').map(Number))
    .filter((v) => v[1] <= d)
    .sort((a, b) => {
        if (a[0] === b[0]) {
            if (a[1] === b[1]) {
                return a[2] - b[2];
            }
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });

const combinations = [];
const makeCombinations = (arr) => {
    if (arr.at(-1) >= infos.length - 1) return;
    let start = arr.at(-1) + 1 || 0;
    for (let i = start; i < infos.length; i++) {
        if (arr.includes(i)) continue;
        combinations.push([...arr, i]);
        makeCombinations([...arr, i]);
    }
};

makeCombinations([]);
console.log(combinations.length);

let answer = d;

for (const combi of combinations) {
    let current = 0;
    let sumCost = 0;
    for (const idx of combi) {
        const [start, end, cost] = infos[idx];
        if (current > start) break
        if (start > current) {
            sumCost += start - current;
        }

        sumCost += cost;
        current = end;
    }
    if (current < d) {
        sumCost += d - current;
    }
    answer = Math.min(answer, sumCost);
}

console.log(answer);