[JS] 점프와 순간이동

 

 

난이도: Lv.2

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

프로그래머스

 

 

알고리즘

결론부터 말하면 입력으로 주어진 N을 2진수로 변환했을 때의 1의 개수가 건전지 사용량과 동일하다.

순간이동을 하는 위치가 현재까지 온 거리의 두 배이기 때문이다.

 

두 가지 경우를 생각해 보자. (n은 짝수로 가정, n이 홀수면 상황이 반대)

1. n까지 가야하는데, n/2까지 왔을 때

→ 순간이동

2. n+1까지 가야하는데, n/2까지 왔을 때

→ 순간이동 후 한 칸 점프

n을 2로 나누었을 때 나머지가 0이라면 건전지를 사용하지 않고, 나머지가 1이라면 점프를 한 번 하므로 건전지를 1 사용한다. 이 과정을 계속하며 건전지 사용량이 0인지 1인지 나열해 보자. 그럼 결국 2진수와 동일한 것을 알 수 있다.

 

현재까지 온 거리의 몇 배에 해당하는 위치로 순간이동 하느냐에 따라 사용해야 하는 진법이 달라지는 문제다.

 

 

코드

function solution(n) {
    var ans = 0;

    while (n > 0) {
        if (n % 2) { ans++; }
        n = Math.floor(n / 2)
    }

    return ans;
}

 

 

 

주저리

문제 보고 제일 처음 한 생각은 시프트 연산을 쓰면 될 것 같다였는데 시프트 연산은 정수 나눗셈이니까 나머지 계산하는 게 귀찮아서 패스하고 +1, *2 이런 거 노트에 끄적이다가 문득 2진수로 써보면 답이 나올 거 같다는 생각이 들었다. 그게 정답이긴 했지만 이유를 설명 못하겠어서 문제는 어제 풀었지만 오늘 올린다.