[실버] 1로 만들기 (1563번)_JS

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

내 답안:
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim() ;
let arr = [] ;

for (let i = 1 ; i <= +input ; i++ ){
    if ( i == 1 ) arr[i] = 0 ;
    else {
        ret = arr[i-1] ;
        if ( i%2 == 0 ) ret = Math.min(ret, arr[i/2]) ;
        if ( i%3 == 0 ) ret = Math.min(ret, arr[i/3]) ;
        arr[i] = ret+1 ;
    }
}

console.log(arr[+input]) ;

 

 

>> 아래는 실패답안

내 답안인데 오류(StackSizeExceeded):
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim() ;
let arr = [] ;

function makeOne(x){ //return = 실행횟수
    if ( arr[x] !== undefined ) return arr[x] ;
    if ( x == 1 ) return 0 ;
    ret = makeOne(x -1) ;
    if ( x%2 == 0 ) ret = Math.min(ret, makeOne(x/2)) ;
    if ( x%3 == 0 ) ret = Math.min(ret, makeOne(x/3)) ;
    arr[x] = ret+1 ;
    return ret+1 ;
}

console.log(makeOne(+input));
>> 재귀라서 그런지 안돌아감