[JS] 점프와 순간이동

시간 효율성을 생각하기 위해서 많이 고민했던 문제였다.

 

 

 

맨 처음에는 재귀를 활용해서 풀어보려고 했다.

 

 

재귀로 모든 경우의수를 찾아보려고 했는데 케이스가 10억까지기 때문에 생각한데로 5000만 넣어도 시간초과가 발생했다.

 

 

두번째로 생각했던 방법은 dp를 활용한 것이었다..

 

 

function solution(n)
{
   
    const dp = new Array(n+1).fill(Infinity)
    dp[0] = 0
    
    for (let i = 1 ; i < dp.length ; i++) {
       
        if (i%2) dp[i] = dp[(i-1)/2] + 1
        else dp[i] = dp[i/2]
        
        for (let j = i-dp[i] ; j < i ; j++){
            if (dp[j] + i-j < dp[i]) dp[i] = dp[j] + i - j
        }
        
    }
    
    
    return dp[dp.length-1]
    
}

 

텔레포트를 하는 경우와 k번 더하는 경우들을 고려했었다. 기본 케이스들은 모두 통과했지만 효율성 테스트를 통과하지 못했다.

 

반복문 하나로 어떻게 하면 줄일 수 있을까 고민을 하다가 결국 최소의 수를 찾기 위해서는 텔레포트를 많이 해야하지 않나? 라는 결론이 나왔다.

 

 

따라서 k번 더하는 것 외에 짝수면 텔레포트, 홀수면 -1한 값에 텔레포트하도록 코드를 바꿔주었다.

 

 

 

function solution(n)
{
   
    const dp = new Array(n+1).fill(Infinity)
    dp[0] = 0
    
    for (let i = 1 ; i < dp.length ; i++) {
       
        if (i%2) dp[i] = dp[(i-1)/2] + 1
        else dp[i] = dp[i/2]
        
    }
    
    
    return dp[dp.length-1]
    
}

 

시간복잡도가 n으로 줄어들었기 때문에 통과할 줄 알았는데 이 코드 역시 통과하지 못했다.

 

 

시간복잡도를 n보다 줄여야 하다니.. 고민을 하다가 굳이 모든 경우의 수를 찾느게 아니라 위 과정을 역으로 진행하면 되는구나.. 라는 생각이 들었다.

 

 

function solution(n)
{
   
    
    let ret = 0
    
    while (n > 0) {
        if (n%2) {
            n = (n-1) / 2
            ret +=1
        } else n = n/2
    }
    
    
    return ret
    
}

 

 

찾는과정을 역으로 했더니 해결되었다.

 

 

생각해보면 쉬운 문제인데 너무 어렵게 돌아갔던 문제였다.