[프로그래머스] Lv2. 숫자 변환하기 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 숫자 변환하기

문제

(https://velog.velcdn.com/images/tngustkdehs/post/c17df282-81fa-4ee7-9b6f-aaa6a56774e3/image.png)

제한사항

📌 내가 생각한 풀이

처음에는 DFS문제로 생각하여 풀기시작했다. 하지만 결과는 런타임에러와 시간초과였다. 어떻게 풀어야할까 고민하다가, 최소경우의수.... 무엇가 DP가 생각났다. arr[i] => i번째 값을 도달하기 위한 최소값이라고 생각하고, y번째 값까지 가는 경우를 배열에 저장하자.

//dp로 풀자
//arr[i] => i번째 값을 취하는데 최소값
function solution(x, y, n) {
    let answer = 0;
    if(x >= y) return answer = 0;
    let arr = new Array(y+1).fill(Infinity);
    arr[x] = 0;
    for(var i = x+1; i<=y; i++){
        if(x <= i-n ) arr[i] = Math.min(arr[i], arr[i-n]+1);
        if(i % 3 ===0 && x <= i/3) arr[i] = Math.min(arr[i], arr[i/3]+1);
        if(i % 2 === 0 && x<= i/2) arr[i] = Math.min(arr[i], arr[i/2]+1);
    }
    return arr[y] === Infinity ? -1 : arr[y]
}

📌 느낀점

처음엔 dfs로 풀어야지 생각했지만, DP로 푸는 것이 더 효율적이였다.
아직 점화식 세우는게 조금 부족한 것 같아, DP문제를 좀더 많이 풀어봐야겠다.
그래도 DP에 대해서 천천히 내꺼화 하는것 같아서 뿌듯하다.