Programming Challenges #27

문제

n명의 사람들로 구성된 한 그룹이 밤중에 다리를 건너려고 한다. 한 번에 최대 2명까지만 다리를 건널수 있으며 다리 위를 지나가는 사람들은 반드시 플래시를 가지고 가야 한다. 그 n명의 사람들한테는 플래시가 한 개밖에 없기 때문에 다른 사람들이 다리를 건너려면 어떤 식으로든 플래시를 가지고 다시 다리를 건너지 않는 사람들이 있는 곳으로 돌아가는 일을 해야 한다. 사람마다 다리를 건너는 속도가 다른데, 그룹의 속도는 가장 느린 구성원의 속도에 따라 결정된다. 가장 짧은 시간 안에 n명이 모두 다리를 건널 수 있는 방법을 결정해야 한다.

해석

가장 짧은 시간 안에 n명이 모두 다리를 건너는 방법을 결정하기 위해서는 다음과 같은 전략을 사용할 수 있습니다:

1. 사람들을 속도 순으로 정렬합니다.
2. 가장 빠른 두 명을 선택하여 다리를 건넙니다.
3. 둘 중 한 명은 다시 플래시를 가지고 돌아갑니다.
4. 다른 빠른 사람이 다리를 건너면, 플래시를 가지고 다시 돌아갑니다.
5. 가장 느린 사람과 플래시를 가지고 다시 다리를 건넙니다.
6. 위의 과정을 반복하여 모든 사람이 다리를 건널 때까지 진행합니다.

이러한 전략을 사용하면 가장 짧은 시간 안에 n명이 모두 다리를 건널 수 있습니다. 이 전략을 구현한 코드는 다음과 같습니다:

function crossBridge(speeds) {
  const n = speeds.length;
  let time = 0;

  // 사람들을 속도 순으로 정렬
  speeds.sort((a, b) => a - b);

  while (n > 0) {
    // 가장 빠른 두 명 선택
    if (n >= 2) {
      const fastest = speeds.shift();
      const secondFastest = speeds.shift();
      time += secondFastest;

      // 둘 중 한 명은 플래시를 가지고 돌아감
      time += fastest;
    }

    // 가장 느린 사람과 플래시를 가지고 다시 다리를 건넘
    else if (n === 1) {
      time += speeds.shift();
    }

    n -= 2;
  }

  return time;
}

// 입력 받기
const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.question("사람의 수를 입력하세요: ", (n) => {
  const speeds = [];

  const getSpeed = (i) => {
    rl.question(`${i + 1}번째 사람의 속도를 입력하세요: `, (speed) => {
      speeds.push(Number(speed));

      if (speeds.length < n) {
        getSpeed(i + 1);
      } else {
        rl.close();

        // 가장 짧은 시간 안에 n명이 모두 다리를 건너는 방법 계산
        const minTime = crossBridge(speeds);
        console.log(`가장 짧은 시간: ${minTime}`);
      }
    });
  };

  getSpeed(0);
});