점프와 순간이동

문제정의

---

k칸 앞으로 점프하는 경우 k만큼 건전지를 사용하고 워프를 통해 현재위치의 두배에 해당하는 위치로 비용없이 간다고 할 때, 목표 지점 n으로 이동하는 최소 건전지 사용량을 구하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

public class JumpAndTele {

    //프로그래머스 문제풀이 Level2 점프와 순간 이동

    public static void main(String[] args) {
        int n = 5000;
        System.out.println(Integer.bitCount(n));
    }
    
}

코드가 너무 간단해서 황당할 수 있다. 자바에는 bitCount란 메소드가 있다. 수를 넘겨주고 이를 2진수로 바꿨을 때 1의 개수를 반환하는 프로그램이다. 이것이 왜 성립하는지 알아보자.

일단 워프를 최대한 많이 쓰는 것이 좋은 것은 자명하다. 그렇다면 이를 어떻게 쓰냐는 건데, 5를 예로 들어보자 5로 가는 가장 빠른 방법은 2에서 워프를 하고 1을 더하면 된다. 2에 도달하는 방법은 1에서 워프를 타면 된다. 그렇다면 0에서 1로는 1만 더하면 된다. 이 방법이 이진법에서 1의 개수를 세는 것과 같다.

최종 시간복잡도는 2진법을 계산하는 과정이 있기 때문에 \(O(log_{2}n)\)이다.

테스트

원래는 \(O(n)\)까지 복잡도를 줄여봐도 효율성이 개선이 안되었다. 10억이나 되기 때문이다. 남자친구랑 점심먹으면서 이 얘기를 하다가 남자친구의 힌트로 허무하게 문제를 풀었다. 역시 수학은 중요하다.