[Programmers] 점프와 순간이동 - Java

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

프로그래머스

---

1. 문제

목표지점 N이 주어진다.

N까지 가기 위해 사용하는 배터리 사용량이 최소가 될 때의 사용량을 출력한다.

점프 - 온 만큼 거리 + 1 -> 배터리 사용량 + 1

순간이동 - 온 만큼 거리 * 2 -> 배터리 사용량 그대로

N은 최대 10억이다.

 

2. 풀이

처음에는 DFS로 접근했다. 하지만 N은 최대 10억이었고, N이 5000일 때도 시간초과가 났다.

단단히 오해를 했던 접근이었다.

최소한의 배터리 사용량을 구하는 것이기 때문에 온 만큼의 거리*2 를 최대한 활용해야 한다.

즉, 2의 배수면 2로 최대한 나누어 떨어진 값을 구하고 거기서 사용량을 구하는 top-down 방식을 사용하는 것이 효율적이었다. 이 부분은 다른 블로그를 참고했다.

 

3. 코드

import java.util.*;
import java.io.*;

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;
    }
}

 

4. 요약

아주 간단한 문제지만 새롭게 접근하면 풀 수 있는 확률이 높아지는 것 같다.

bottom-up 보다 top-down 방식이 경우의 수가 더 줄어들 때가 있다.