프로그래머스 Lev 2 - 숫자 변환하기

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다
• x에 3을 곱합니다
  자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

접근법

일단 각 값에서 할 수 있는 연산은 2,3,+5 세가지를 통해 결과값이 총 3개가 나오고, 이 연산들 각자 또한 세가지 연산을 통해 ... 계속 갈 수 있음
10에서 할 수 있는 일은 15,20,30 - 15는 또 20,30,45 - ... 계속 가기 때문에 어찌보면 백트래킹으로 풀 수 있지 않을까 라는 생각을 해봄
bfs보다는 dfs가 더 맞다고 생각해서 해봤는데 시간초과가 뜨길래(나중에 보니까 코드만 좀 수정하면 이렇게도 풀 수 있다고 함) dp로 바꿔서 생각해봄

y=40이라고 가정하면, y는 20까지 구한 최소 연산횟수에서 +1을 하거나 , 40-n까지 구한 최소 연산횟수에서 +1을 하거나 , /3을 한 최소 연산은 없기 때문에 저 두가지 값들 중 최솟값을 구해주면 됨

dp[i] = x를 i로 변환하기 위해 필요한 최소 연산 횟수
dp[i] = Math.min(dp[i-n],dp[i/2],dp[i/3]) + 1

코드

function solution(x, y, n) {
  const dp = Array(y+1).fill(-1);
  dp[x] = 0;
  for (let i = x + 1; i <= y; i++) {
    const arr = [];
    if (dp[i - n] >= 0) {
    arr.push(dp[i - n]);
    }
    if (i % 2 === 0 && dp[i / 2] >= 0) {
      arr.push(dp[i / 2]);
    }
    if (i % 3 === 0 && dp[i / 3] >= 0) {
     arr.push(dp[i / 3]);
    }
    if (arr.length) {
      dp[i] = Math.min(...arr) + 1;
    }


}
    return dp[y]
}

dp라는 배열을 dp[x]를 제외한 나머지를 -1로 초기화해주고, x+1부터 y까지 반복문을 통해서 dp를 채워줌
여기서 세 가지의 연산으로는 만들 수 없는 값들이 존재함
ex)x=10,y=40,n=5 일 때 x=11,12는 만들 수 없음
이런 값들은 그대로 -1로 두고, 나중에 dp[22] 같은 곳에서 이 값을 참조하기 못하게 조건문을 걸어주고
진짜 비교할 수 있는 값들만 arr이라는 배열에 넣고, 제일 마지막에 최종적으로 최솟값을 구한 다음 +1을 해줌