문제

코드

function solution(x, y, n) {
    if (x === y) return 0;

    const dp = {};

    dp[x] = 0;

    let data = [x];

    while (data.length) {
        const newData = [];

        for (const d of data) {
            for (const e of [d + n, d * 2, d * 3]) {
                console.log(d, e, dp);
                if (e > y || dp[e]) continue;
                if (e === y) return dp[d] + 1;
                dp[e] = dp[d] + 1;
                newData.push(e);
            }
        }
        data = newData;
    }

    return -1;
}

시간초과 된 내 풀이

• 나름 머리 써서 y에서 x로 돌아가는 방법으로 풀었어요! (현재 숫자가 2나 3으로 나누어 떨어지지 않으면 절차를 생략해도 되니까요!) 진짜 어쩜 이렇게 똑똑할까
• 물론 시간초과구요~

dp를 이용한 풀이

• dp를 만들어 두고, 숫자가 지날 때마다 그 숫자 속성에 이전 move count에서 +1을 한 값을 value로 넣어줘요
• 이중 포문을 위해 data 배열을 선언해요

여기서 꿀팁! for문이 제일 빠르대서 항상 일반 for만 썼는데 for of랑 forEach도 충분히 빠르다고 하니 많관부

• 두 번째 포문에 날 것으로 [d+2, d*2, d*3]을 넣어준 것이 감명 깊었어요.
• dp[e]가 있거나 값을 초과하면 continue
• dp[e]가 없으면 현재 move count인 dp[d]값에 +1을 하여 할당
• e === y 면 원하는 답이니까 return dp[d]+1을 해줘요!
• 다 돌았는데 안 나온다? 그럼 -1