[JS]프로그래머스 Level2.숫자 변환하기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=javascript

---

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

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

---

제한사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

---

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

---

첫번째 풀이 (DFS)

dfs로 접근해서 문제 풀이

(50/100) 시간초과,런타임 에러

function solution(x, y, n){
	 function dfs(val,count){
    if(val == y ){
      arr.push(count);
    }else if(val < y){
      dfs(val*2,count+1);
      dfs(val*3,count+1);
      dfs(val+n,count+1);
    } 
  }
  dfs(x,0);

  return arr.length ? Math.min(...arr) : -1; 

}

두번째 풀이 (DP)

dp로 접근해서 문제 풀이

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

dp 라는 Array에 무한한 값이 Infinity를 채운후 n으로 minus일시
2,3으로 곱할시 count 후 Math.min을 통하여 제일 낮은 횟수의 방법을 가지고 계속 진행 한 후 마지막값에 담는 형식으로 구현