점프와 순간 이동 [역방향으로 생각하기]

https://school.programmers.co.kr/learn/courses/30/lessons/12980?language=java

프로그래머스

💡 핵심 아이디어

건전지를 가장 적게 사용하려면 한 칸 이동은 최대한 적게 하고, 순간이동을 최대한 많이 해야 한다.

순간이동은 현재 위치의 2배로 이동하기 때문에, 0에서는 순간이동을 해도 계속 0이다.
따라서 시작할 때는 최소 한 번 1칸 이동해야 한다.

목적지에서 거꾸로 생각하면 간단하다.

• 짝수라면 → / 2 → 순간이동으로 온 것
• 홀수라면 → - 1 → 순간이동으로는 홀수가 될 수 없으므로 한 칸 이동해서 온 것

따라서 목적지에서 시작해서 0이 될 때까지 반복하면 된다.

 

✨ 배운 점

앞으로 비슷한 문제에서

"정방향으로 최적의 선택을 찾기 어렵다면, 목적지에서 시작점으로 거꾸로 생각해보자."

라는 접근을 떠올려보기.

 

시간복잡도 : O(logN) 

이유: /2 하는 부분때문에 n 이 계속 절반수준으로 줄어들기 때문에

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;
        while(n != 1){
            if(n%2 ==0){
                //짝수
                n /= 2;
            } else {
                // 홀수
                n -= 1;
                ans++;
            }
        }
        ans += 1;
        return ans;
    }
}