[JS] 2Level / 연습문제 / 숫자 변환하기

문제 설명

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

프로그래머스

 

문제 풀이 방법

• 처음 문제를 보고 dfs나 bfs를 이용해 문제를 풀이할까 생각했지만,
  제한 사항을 보면 x와 y의 크기가 최대 1,000,000까지인걸 보면 시간복잡도를 생각해 시간초과 오류를 고려해
  이전 계산 결과를 이용하는 DP를 이용해 풀기로 했다.
• 동작 시간을 줄이기 위해 for문에서 해당 칸이 -1인 곳은 건너 뛰고 다음 동작을 하게 해준다.

 

코드 

const solution = (x, y, n) => {
    let dp = Array(y+1).fill(-1);
    dp[x] = 0;
    
    for(let i=x; i<=y; i++){
        if(dp[i] === -1) continue;
        if(i + n <= y){
            if(dp[i + n] === -1){
                dp[i + n] = dp[i] + 1;
            }
            else{
                dp[i + n] = dp[i + n] < dp[i] + 1 ? dp[i + n] : dp[i] + 1;
            }
        }
        if(i * 2 <= y){
            if(dp[i * 2] === -1){
                dp[i * 2] = dp[i] + 1;
            }
            else{
                dp[i * 2] = dp[i * 2] < dp[i] + 1 ? dp[i * 2] : dp[i] + 1;
            }
        }
        if(i * 3 <= y){
            if(dp[i * 3] === -1){
                dp[i * 3] = dp[i] + 1;
            }
            else{
                dp[i * 3] = dp[i * 3] < dp[i] + 1 ? dp[i * 3] : dp[i] + 1;
            }
        }
    }

    return dp[y]
}