(JavaScript) 숫자 변환하기

문제

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

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

---

해결

 첫 숫자 X로부터 출발해 재귀적으로 백트래킹을 적용해 최소 횟수를 찾는다.

코드

function solution(){
	var answer = -1;
  	const foo = (num, count) => {
        if(answer !== -1 && count >= answer) return;
        if(num > y) return;
        if(num === y) {
            if(answer === -1) answer = count;
            answer = count < answer ? count : answer;
            return;
        };
        foo(num + n, count + 1);
        foo(num * 2, count + 1);
        foo(num * 3, count + 1);
    }
    foo(x, 0);
    return answer;
  }

결과

실패(시간초과, 런타임에러)

이유

문제의 조건

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

에 따르면 x, y의 숫자가 너무 커서 스택 오버플로우가 걸리는게 아닐까 싶다. 특히 함수의 호출 순서가 +n인 경우가 먼저이기 때문에 더욱 그렇지 않을까싶다.

---

해결2

 함수의 호출 순서를 바꿔서 시도해보기 보다는 그냥 방법 자체를 바꾸기로 했다. 백트래킹 대신 dp를 적용한다. y길이의 배열을 -1로 초기화 하고, 인덱스까지의 연산 횟수를 저장한다. 즉 dp[x] = 0 이다.

 이후 인덱스를 1씩 증가시키며, 인덱스 i에 대하여 dp[i-n], dp[i/2], dp[i/3] 이 -1이 아닌 경우, 셋 중 최소값에 1을 더해서 dp[i]에 저장한다.

 이 경우 시간복잡도는 O(n)이 된다.

코드

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

결과

성공