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

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

문제풀이

개인적으로 이런 문제가 정말 어렵다. 문제를 처음 훑어봤을 때 BOJ 숨바꼭질 유형의 문제라고 생각했고 BFS, DFS를 적용해보려 노력했지만

• 최악의 경우가 10억이고
• 먼저 도착하는 것이 아니라 배터리를 최소로 사용하는 것이다 보니
• 각 depth에서 너무나 많은 경우의 수가 존재했다.

따라서 불가능했다. 그러던 중 배터리를 최소로 사용해야함에 집중해서 다시 생각해봤다. 그렇다면 순간이동을 최대한 많이 사용하고 점프를 최소로 사용해야했다. 그리고 문제를 다시 읽으며 중요점을 체크했다.

• N의 위치에 정확하게 도착해야한다.
• 거리는 자연수다.

그리고 이전에 풀었던 문제 BOJ A->B에서 bottom-up 보다는 top-down 방식이 경우의 수가 훨씬 줄어드는 것이 떠올라 대입해봤다.

정리하자면

• 주어진 N이 0이 될 때까지 다음 연산을 반복한다.
  • N이 짝수면 N /= 2
  • N이 홀수면 N -= 1

몇 칸 점프를 할 것인가 또는 순간 이동할 것인가의 많은 경우의 수를 현재 N이 짝수인가 홀수인가의 두 가지 경우의 수로 줄일 수 있었고 bottom-up에서 N을 넘는 경우를 생각해야했다면 top-down에서는 0보다 작아지는 경우가 없기 때문에 생각할 필요가 없었다.

구현코드

import java.util.*;

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

        return ans;
    }
}