[PRO] 프로그래머스 Lv.2 숫자 변환하기 (Javascript)

문제

프로그래머스

 

 

문제 해석

접근 방법

어떤 숫자를 다른 숫자로 변환하기 위해 드는 최소 연산 횟수를 계산합니다.

최소 연산 횟수를 찾기 위해 BFS 혹은 DP를 사용할 수 있습니다.

 

풀이 과정

1. BFS로 풀이 : 일부 시간 초과

function solution(x, y, n) {
    let [nx, cnt] = [x, 0];
    const q = [[nx, cnt]];
    while (q.length) {
        [nx, cnt] = q.shift();
        if (nx === y) return cnt;
        cnt++;
        if (nx + n <= y) q.push([nx + n, cnt]);
        if (nx * 2 <= y) q.push([nx * 2, cnt]);
        if (nx * 3 <= y) q.push([nx * 3, cnt]);
    }
    return -1;
}

 

 

2. DP로 풀이 (최종 정답)

전체 코드

function solution(x, y, n) {
    const memo = new Array(y + 1).fill(-1);
    memo[x] = 0;
    while (x < y) {
        if (memo[x] > -1) {
            const arr = [x + n, x * 2, x * 3];
            arr.forEach((a) => {
                if (a <= y) {
                    memo[a] =
                        memo[a] === -1
                            ? memo[x] + 1
                            : Math.min(memo[a], memo[x] + 1);
                }
            });
        }
        x++;
    }
    return memo[y];
}

 

회고