문제

문제 풀이

점프는 배터리 이동 거리만큼 소모하지만 순간이동은 소모하지 않으므로, 최소한의 배터리로 이동하기 위해선 순간이동을 최대한 많이 활용 해야 한다.

---

풀이

반대로

순간이동은 무조건 왔던 거리의 두배만큼 갈 수 있다. 즉 시작점부터 도착점까지
1.맞게 도착하는지
2.넘어가는지
3.부족한지
비교하며 점프와 순간이동 하는 것보단 도착지점에서 출발점으로 거꾸로 진행하면 쉽게 구할 수 있을 것이다.

이진법

거꾸로 연산을 하면, 남은 값이 최대일때 나누기 2하는것이 순간이동의 효율이 최대일 것이다. 나머지가 있으면 그때만 1만큼 점프하면 다시 나누기 2의 효율이 최대가 될것이고 순간이동의 효율이 최대, 배터리 소모 최소가 될것이다.

	for(int i = n; i > 0; i=i/2)
       if((i%2)==1) //순간이동후 나머지
           ans++; //점프

---

코드

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;
        //거꾸로 순간이동을 최대한 많이 함 == 최소의 에너지
        for(int i = n; i > 0; i /= 2){
            if(i % 2 == 1) ans++;
        }
        return ans;
    }
}

---

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%9E%90%EB%B0%94/Level2/%EC%A0%90%ED%94%84%EC%99%80%EC%88%9C%EA%B0%84%EC%9D%B4%EB%8F%99.java