[프로그래머스] 점프와 순간이동

문제링크

( https://school.programmers.co.kr/learn/courses/30/lessons/12980 )

1. 풀이 힌트

 - 순간이동을 최대한 많이 해야하므로 n에서 2를 나눈다. 

 - 나누어 떨어지지 않는다면 점프를 해야하는 구간이므로 answer을 카운트 한다.

 - 몫이 0이 되면 카운트한 answer을 출력한다.

2. 코드 풀이

function solution(n) {
    let answer = 0;
    while(n > 0) {
        if(n % 2 === 0) {
            n /= 2;
        } else {
            n--;
            answer++;
        }
    }
    
    return answer;
}

3. 회고

- 처음에는 0부터 세는 방식으로 접근했다. 각 step에서 점프와 순간이동을 호출하는 재귀 함수를 구현했다. 결과는 시간초과. 각 step의 최소 시간을 저장하는 DP 방식으로 시간을 좀 줄였지만 그래도 시간 초과가 났다. 좀 더 고민하다가 다른 사람 풀이를 봤는데 답은 생각보다 간단했다... 키포인트는 n번째 부터 내려가는 방식으로 생각하는 방법인 것 같다.

- 좀 더 깔끔하게 푼 사람들은 이진법으로 변환한 뒤 1의 숫자를 세는 방식으로 풀었다. (그런 생각을 해내는게 대단하다)