Level 2️⃣ - 숫자 변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

🚀문제 해석

사용할 수 있는 연산은 세가지이다.

- X에 n을 더한다.

- X에 2를 곱한다.

- X에 3을 곱한다.

따라서 다음과 같은 그래프 그림으로 표현할 수 있다.

따라서 BFS를 구현해서 최단거리를 구하려고 시도했다.

function solution(x, y, n) {
    let visited = Array.from({length: 1_000_001}).fill(0);
    function bfs(here){
        const queue = [];
        visited[here] = 1;
        queue.push(here);
        while(queue.length) {
            const elem = queue[0];
            if(elem === y) return;
            queue.shift();
            if((elem + n) > y && (elem * 2) > y && (elem * 3) > y) return -1;
            if(!visited[elem + n]) visited[elem + n] = visited[elem] + 1;
            if(!visited[elem * 2]) visited[elem * 2] = visited[elem] + 1;
            if(!visited[elem * 3]) visited[elem * 3] = visited[elem] + 1;
            queue.push(elem + n);
            queue.push(elem * 2);
            queue.push(elem * 3);
        }
    }
    bfs(x);
    return visited[y] - 1;
}

하지만 실패한 케이스도 있었고, 시간초과가 나왔다.

예상해보니 최악의 경우 x가 1이고 n이 1일때 y가 100만일 수 있다. 그때마다 가지를 뻗어가며 BFS 탐색을 하면 시간복잡도가 크게 늘어난다. 그리고 queue를 사용하는 부분에서 탐색을 할 때마다 shift 연산을 하기 때문에 복잡도가 늘어날 수 있다. 처음에는 하나씩만 빼는데 크게 늘어날까 생각했지만 가지를 엄청나게 뻗어가면 큐에 들어가는 데이터의 양도 많아지기 때문에 뒤로 갈수록 shift 연산에 무리가 갈 수 있다는 생각을 했다.

 

🎯DP로 접근하기

그래프 탐색에서 시간복잡도의 문제가 발생하면 DP로 접근해봐야한다.

메모이제이션을 활용할 것이다.

먼저 숫자의 범위는 x부터 y까지이다. 따라서 for 문을 사용해 x부터 y까지 탐색한다. 탐색 요소를 i라고 해보자.

그리고 dy 배열을 만들어 dy[i]는 x에서 i까지의 최소 연산갯수를 넣어준다.

어떻게 넣어줄 수 있을까?

먼저 dy[x] = 0을 넣어준다.

그리고 i가 x+n이 되면 dy[x]에 있던 값에서 1을 늘려서 dy[i]에 넣어주면 된다.

또 i가 x+n+n이 되면 dy[x+n]에 있던 값에서 1을 늘려서 dy[i]에 넣어주면 된다.

function solution(x, y, n) {
    let d = [...Array(y + 1).fill(Number.MAX_SAFE_INTEGER)];
    d[x] = 0;
    
    for(let i = x; i <= y; i++){
        if(i - n >= x) d[i] = Math.min(d[i], d[i - n] + 1);
        if(i % 2 === 0 && i / 2 >= x) d[i] = Math.min(d[i], d[i / 2] + 1);
        if(i % 3 === 0 && i / 3 >= x) d[i] = Math.min(d[i], d[i / 3] + 1);
    }
    
    return d[y] === Number.MAX_SAFE_INTEGER ? -1 : d[y];
}