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

문제

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

코딩테스트 연습 - 점프와 순간 이동

설명

건전지 사용량의 최솟값을 구하기 위해서는 건전지 소모가 되지 않는 순간이동을 많이 쓰고 점프를 최소화해야 한다!

 

예를 들어 n이 6일 때 6까지 최대한 순간이동을 해보자!

그러기 위해 6에서부터 0까지 Top-Down 방식으로 생각해보자

(0부터 6까지 Down-Top으로 생각한다면 머리 아프다... 복잡함. 6을 넘어가는 경우도 생각해야 하고 6부터 내려오면서 0까지 떨어뜨리는 게 훨씬 편함)

 

 

먼저 6까지 최대한 많은 거리를 순간이동을 통해서 오려면 3에서 순간이동을 하면 된다. (6 -> 3 건전지 소모 X)

(즉 0부터 3까지 점프를 하든 순간이동을 하든 어떻게든 3까지에서 오고 3만큼 순간이동으로 6까지 가면 최대한 많은 거리를 순간이동할 수 있다는 것!)

 

 

그럼 3까지로 순간이동을 하려면 어디서? 해야 하나?

할 수 없음! 무조건 점프가 하나 추가되어야 함

그럼 2에서 1만큼 점프해서 3이 됐다고 생각하면 (3 -> 2 건전지 소모 1  / 점프 1회)

 

 

그럼 2는 1에서 1만큼 순간이동을 하면 된다 (2 -> 1 건전지 소모 X)

 

 

 

그리고 마지막 1은 처음 0에서 무조건 1만큼 점프를 해주어야 함 (그래야 순간이동이든 점프든 n값까지 나아갈 수 있겠죠?)

(1 -> 0 건전지 소모 1 / 점프 1회)

 

 

결론적으로 총 2만큼의 건전지가 소모된다!

 

소감 : 나는 처음에 1만큼 점프해보기... 2만큼... 3만큼... 어 n값 넘어가면 다시 돌아오고 등등 Down-Top으로 생각하면서 굉장히 골머리를 앓았다. 그리고 막상 풀고 나서는 너무 허탈할 정도로 간단?! 했던 문제ㅠ_ㅠ

결론

N이 0이 될 때까지

N이 짝수라면 반을 나누고 N / 2 (순간이동)

N이 홀수라면 -1을 빼며 (점프)

최솟값을 구하는 것이다!

전체 코드

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 -= 1;
                ans++;
            }
        }
    
        return ans;
    }
}