[node.js] 점프와 순간 이동 ( 프로그래머스 레벨2 )

// 프로그래머스 레벨2 점프와 순간 이동을 풀었습니다.
const solution = (n) => {
//     const visited = new Array(n + 1).fill(0).map((el, i) => i);

//     const dfs = (cur) => {        
//         for (let i = 1; 2 ** i * cur <= n; i++) {
//             if (visited[cur] < visited[2 ** i * cur]) {
//                 visited[2 ** i * cur] = visited[cur];
//                 dfs(2 ** i * cur);
//             }
//         }

//         if (visited[cur] + 1 < visited[cur + 1]) {
//             visited[cur + 1] = visited[cur] + 1;
//             dfs(cur + 1);
//         }
//     }
//     dfs(1);

//     console.log(visited);
//     return visited[n];

    return Number(n).toString(2).split('').filter((el) => el == 1).length;
}

dfs로 시간 초과가 떠서 bfs로 고치고, 최적화를 위해서 별 짓을 다 했는데도 시간 초과는 사라지지 않았다.
혹시 그래프적인 방법 외에도 뭔가 있나 고민해봤는데, 2로 나눴을 때의 나머지가 1인 횟수가 아무래도 답인 거 같다.
그래서 2진수로 변환하여 구했다.