(Java) 프로그래머스 - 점프와 순간 이동

문제를 보자마자 Dp라는걸 알았다.

난이도도 레벨2에 있기에는 너무 쉬운 문제였다고 생각한다.

bottomUp 방식과 TopDown 모두 가능하지만 Topdown 방식이 더 간단해 보여서 Topdown을 이용해서 풀었다.

 

로직은 2로 나누어 떨어진다면 순간이동이 가능하다는 것이므로 n에서 2로 나누어준다.

그게 아니라면 한칸을 점프하고 다시 시도한다.

최종적으로 n이 0인 시작점으로 돌아온다.

---

최종 코드

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;

        // dp (top-down)
        while (n > 0) {
            // 2로 나누어 떨어진다는것은 순간이동이 가능
            if(n % 2 == 0) {
                n /= 2;
                // 아니면 점프 한칸
            } else {
                n--;
                ans++;
            }
        }

        return ans;
    }
}