숫자 변환하기 (DFS, DP)

숫자 변환하기 문제 보기

---

문제 풀이 1 (실패) DFS

첫 번째로 DFS(깊이 우선 탐색)를 이용하여 재귀적인 방식으로 문제를 해결하려 했습니다.

비효율적인 방법이라는 것은 인지하고 있지만, 일단 구현하기 위해서 시도한 방법입니다.

 

y를 만들 수 있는 가능한 모든 경우의 수를 저장하고, 그 중에서 가장 작은 값을 찾아 반환하기로 했습니다.

그러나 이 방식은 n=1 y=1,000,000인 경우만 생각해보아도 경우의 수가 너무 많습니다.

결과는 예상대로 스택 오버플로우 에러가 발생합니다.

 

이미 계산된 값인 경우에는 종료시켜주기 위해서 Map 객체로 값을 메모하기도 했지만 어림도 없었습니다. 

function solution(x, y, n) {
  let result = [];

  const bfs = (num, count) => {
    // 더 작게 만들 수 없으면 종료
    const minNum = Math.min(num / 2, num / 3, num - n);
    if (num < minNum) {
      return;
    }

    // x를 만들었으면 해당 count 기록
    if (num === x) {
      return result.push(count);
    }

    if (num % 2 === 0) bfs(num / 2, count++);
    if (num % 3 === 0) bfs(num / 3, count++);
    if (num - n > 0) bfs(num - n, count++);
  };

  bfs(y, 0);

  // 가작 작은 count 반환
  return result.length ? Math.min(...result.filter(Boolean)) : -1;
}

solution(2, 5, 4);

---

문제 풀이 2 DP

dfs로는 문제 해결이 안된다는 생각에 다른 사람의 풀이를 보았습니다.

(이미 구한 값을 메모한다는 발상은 DFS + MAP 객체로도 했었지만...)

참고한 이 방식은 메모를 이용하여 O(N)에서 끝내는 효율적인 방법이었습니다. 

 

배열의 Index 자체를 "숫자"로 이용하고,

해당 "숫자"를 구하기 위해 필요한 연산 횟수를 저장하는 방식입니다.

function solution(x, y, n) {
  const dp = Array(y + 1).fill(Infinity);
  dp[x] = 0;

  for (let i = x + 1; i < y + 1; i++) {
    if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    if (i - n >= x) dp[i] = Math.min(dp[i], dp[i - n] + 1);
  }
  return dp[y] === Infinity ? -1 : dp[y];
}

solution(10, 40, 5);

 

풀이 원리 이해

최초에 y+1 길이만큼 배열을 만들어 줍니다. 

x=y인 경우 x를 y로 만들기 위해 필요한 연산 횟수는 0회입니다.

따라서 dp[x] = 0 으로 기록합니다. 

 

x=1, y=8, n=1 일 때, x+n 만으로 x를 y로 만들기

//y=8
const dp = Array(y + 1).fill(Infinity);
dp[x] = 0;

[
  Infinity, Infinity, Infinity,
  Infinity, Infinity, Infinity,
  Infinity, Infinity, Infinity,
]

n이 1인 경우, 

x+n 만으로 x를 y로 변환시키기 위해서는 7회를 더해주어야 합니다.

 

다음과 같은 방식으로 연산에 필요한 값을 이용하여 각 Index를 만들기 위해 필요한 연산 횟수를 구할 수 있습니다.

 

dp[2]를 구하기 위해 필요한 연산 횟수는 dp[1]을 구하는데 필요한 연산 횟수 +1 

dp[3]을 구하기 위해 필요한 연산 횟수는 dp[2]을 구하는데 필요한 연산 횟수 +1 

dp[4]를 구하기 위해 필요한 연산 횟수는 dp[3]을 구하는데 필요한 연산 횟수 +1 

...

  for (let i = x + 1; i < y + 1; i++) {
    if (i - n >= x) dp[i] = Math.min(dp[i], dp[i - n] + 1);
  }

[
  Infinity,  0,  1,
         2,  3,  4,
         5,  6,  7,
]

n이 2~6인 경우는 다음과 같이 dp[8]은 건너뛰게 됩니다.

// n=2
[
  Infinity,        0, Infinity,
         1, Infinity,        2,
  Infinity,        3, Infinity,
]

n이 7인 경우에는

dp[8]을 구하기 위해 필요한 연산 횟수는

dp[1]을 구하는데 필요한 연산 횟수 +1 입니다.

[
  Infinity,        0, Infinity,
  Infinity, Infinity, Infinity,
  Infinity, Infinity,        1,
]

둘 이상의 방법을 이용하여 dp[y]를 만들기 위해 필요한 최소 연산 횟수 저장하기

  for (let i = x + 1; i < y + 1; i++) {
    if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    if (i - n >= x) dp[i] = Math.min(dp[i], dp[i - n] + 1);
  }

x+n 에 대해서만 시행했다면 이번에는 문제에서 나온

x*2와 x*3를 함께 시행해보겠습니다.

[
  Infinity, 0, 1,
         1, 2, 3,
         2, 3, 3,
]

dp[8]을 구하기 위해 x+n를 이용하면 다음과 같이 7회의 연산이 필요하지만,

dp[2]를 구하기 위해 필요한 연산 횟수는 dp[1]을 구하는데 필요한 연산 횟수 +1 
dp[3]을 구하기 위해 필요한 연산 횟수는 dp[2]을 구하는데 필요한 연산 횟수 +1 
dp[4]를 구하기 위해 필요한 연산 횟수는 dp[3]을 구하는데 필요한 연산 횟수 +1 
...
dp[8]을 구하기 위해 필요한 연산 횟수는 dp[7]을 구하는데 필요한 연산 횟수 +1

 

x*2를 이용하면 다음과 같이 3회의 연산이 필요합니다.

dp[2]를 구하기 위해 필요한 연산 횟수는 dp[1]을 구하는데 필요한 연산 횟수 +1 
dp[4]를 구하기 위해 필요한 연산 횟수는 dp[2]을 구하는데 필요한 연산 횟수 +1 
dp[8]을 구하기 위해 필요한 연산 횟수는 dp[4]을 구하는데 필요한 연산 횟수 +1

dp[4]를 구하기 위해서 x+n을 이용한 경우에는 3회가 필요했지만

x*2를 이용한 경우에는 2회만 필요합니다.

 

따라서, dp[4]를 구하기 위해 필요한 최소 연산횟수는 2가 되어야 합니다.

 

이렇게 최소 연산 횟수를 메모하기 위해서는 Math.min()을 이용할 수 있습니다.

    if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    if (i - n >= x) dp[i] = Math.min(dp[i], dp[i - n] + 1);

결과를 구할 수 있다면 dp[y]에 최소 연산횟수가 기록되어 있고, 그렇지 않다면 Infinity가 남게 됩니다.

  return dp[y] === Infinity ? -1 : dp[y];