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

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

프로그래머스

코드

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

풀이

규칙을 찾아보면 쉽게 해결할 수 있다.

K칸 점프하면 K만큼의 건전지 사용량이 들고,

(현재위치 * 2) 만큼 순간이동 하면 건전지는 들지 않는다.

따라서 건전지 사용량을 최소로 하려면 순간이동을 가능한 한 많이 해야한다.

 

순간이동은 현재위치 * 2이므로, 2배씩 증가한다.

주어진 n이 0이 될때까지(현재 위치 도착) 끝에서 거꾸로 내려오면서

2로 나누거나(순간이동), 1을 빼주면 된다(K칸 점프)

5000의 경우를 예로들면

2500 

1250

625 -> 624 , 건전지 + 1 , ans = 1

312

156

78

39 -> 38 ,  건전지 + 1 , ans = 2

19 -> 18 ,  건전지 +1 , ans = 3

9 -> 8 ,      건전지 + 1 , ans = 4

4

2

1 -> 0(종료) 건전지 + 1 , ans = 5

따라서 결과는 5가 된다.

 

 

위 코드를 3항연산자를 통해 간결하게 나타냈다.

public class Solution {
    public int solution(int n) {
        int ans = 0;
        while(n!=0){
            ans += (n%2 == 0) ? 0 : 1;
            n = (n%2 == 0) ? n/2 : n-1;
        }
        return ans;
    }
}