[Programmers] 마법의 엘리베이터 - Javascript

INDEX

https://school.programmers.co.kr/learn/courses/30/lessons/148653

프로그래머스

 

 

Solution

엘리베이터는 10의 제곱승만큼 이동할 수 있습니다. 

최소한의 마법의 돌을 사용하기 위해선 10의 제곱승 단위의 층에 빠르게 도달해야 합니다.

16층을 예시로 든다면 우선 처음에는 10(-6) 층으로 갈지 혹은 20(+4) 층으로 갈지 선택해야 하고 

10층에선 1개, 20층에선 2개를 사용하기 때문에 더 적은 돌을 사용하는 16 -> 20(+4) -> 0(-20)가 답이 됩니다.

 

즉, 1의 단위부터 10, 100 단위까지 높여가면서 더 가까운 10의 제곱승 단위 층을 선택하면 됩니다.

16층 예제를 도식화 해보면 다음과 같습니다.

2554층 예제를 도식화 해보면 다음과 같습니다.

예제에서는 빨간색 테두리의 루트를 정답으로 했지만 사실 2554 - 2550(-4) - 2500(-50) - 2000(-500) -0(-2000)의 경로도 총 16개의 돌을 사용해서 갈 수 있으므로 정답이 됩니다.

 

어차피 돌의 최소 개수를 구하면 되는 문제여서 경로는 크게 상관없습니다.

저는 이 문제를 DFS 로 풀었습니다.

 

우선 10의 제곱승 단위로 층을 이동할 수 있기 때문에 50층을 이동했다면 5개의 돌을 사용한 것이고 (10층 * 5) 400 층을 이동했다면 4개의 돌을 사용한 겁니다. (100층 * 4) 

 

사용한 돌의 개수를 반환하는 함수는 다음과 같습니다.

function getStoneCount(n) {
  return Number(n.toString()[0]);
}

층을 문자열로 변환한 다음 첫 번째 문자를 숫자로 변환하여 반환합니다.

 

solution 함수 내부는 다음과 같습니다.

function solution(storey) {
  function dfs(n, digit, cnt) {
    if (digit === storey.toString().length + 1) return cnt + getStoneCount(n);

    const tenPow = Math.pow(10, digit);
    const a = n - (n % tenPow);
    const b = n + (tenPow - (n % tenPow));
    return Math.min(
      dfs(a, digit + 1, cnt + getStoneCount(n % tenPow)),
      dfs(b, digit + 1, cnt + getStoneCount(tenPow - (n % tenPow)))
    );
  }
  return dfs(storey, 1, 0);
}

 

1의 단위부터 비교를 시작하기 때문에 digit이란 parameter를 받습니다.

16층이 storey 로 주어진 다고 하면

a 에는 10이, b에는 20 이 들어갑니다. 다음 dfs 함수에서는 10이 0과 100으로, 20이 0과 100으로 나누어지고 그다음 dfs에서 digit이 3이 되는 순간 dfs가 종료됩니다.

 

전체코드

function solution(storey) {
  function dfs(n, digit, cnt) {
    console.log(n, digit, cnt);
    if (digit === storey.toString().length + 1) return cnt + getStoneCount(n);

    const tenPow = Math.pow(10, digit);
    const a = n - (n % tenPow);
    const b = n + (tenPow - (n % tenPow));
    return Math.min(
      dfs(a, digit + 1, cnt + getStoneCount(n % tenPow)),
      dfs(b, digit + 1, cnt + getStoneCount(tenPow - (n % tenPow)))
    );
  }
  return dfs(storey, 1, 0);
}
function getStoneCount(n) {
  return Number(n.toString()[0]);
}