[백준] 1459

걷기

문제

세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 (X, Y)에 위치한 집으로 가려고 한다. 세준이가 걸을 수 있는 방법은 두가지 인데, 하나는 도로를 따라서 가로나 세로로 한 블록 움직여서 이번 사거리에서 저 사거리로 움직이는 방법이고, 블록을 대각선으로 가로지르는 방법이 있다.

세준이가 집으로 가는데 걸리는 최소시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 위치 X Y와 걸어서 한 블록 가는데 걸리는 시간 W와 대각선으로 한 블록을 가로지르는 시간 S가 주어진다. X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고, W와 S는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 집에가는데 걸리는 최소시간을 출력한다.

풀이

const home = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  let min, max;
  input[0] > input[1]
    ? ((min = input[1]), (max = input[0]))
    : ((min = input[0]), (max = input[1]));
  let time = 0;
  if (input[2] * 2 > input[3]) {
    if (input[2] >= input[3]) {
      if ((min + max) % 2) time = (max - 1) * input[3] + 1 * input[2];
      else time = max * input[3];
    } else time = min * input[3] + (max - min) * input[2];
  } else time = (min + max) * input[2];
  console.log(time);
};

home();

반성회

• 가로세로 이동 시간의 두 배가 대각선 이동 시간보다 길 경우
  • 가로로 한번, 세로로 한번 (총 두번) 이동하는 것보다 대각선으로 한 번 이동하는 게 빠르다
  • 따라서 가로와 세로 중 짧은 길이만큼 대각선으로 이동하고, 나머지 거리만큼 가로세로로 이동하면 된다
    • ⇒ time = min * S + (max - min) * W
• 가로세로 이동 시간이 대각선 이동 시간보다 같거나 길 경우
  • 가로 + 세로 합이 짝수일 경우, 대각선으로 이동할 수 있다
  • 이때 대각선으로 가로와 세로 중 더 긴 길이만큼 이동하면 같은 지점에 도달할 수 있음
    • ⇒ time = max * S
  • 가로 + 세로 합이 홀수일 경우, 가로와 세로 중 긴 길이 - 1만큼 대각선으로 이동한 후 가로 or 세로로 한번 더 이동하면 됨
    • ⇒ time = (max - 1) * S + W
• 가로세로 이동 시간의 두 배가 대각선 이동 시간보다 짧을 경우
  • 대각선으로 이동할 바에 가로세로로 이동하는 게 더 빠름
    • ⇒ time = (max + min) * W