프로그래머스 [점프와 순간 이동] - 구현 Lv.2

구현

• 문제가 제시하는 규칙성을 파악하고, 조건에 맞춰 답을 반환하는 문제이다.

규칙성 파악, 로직

• 처음 문제를 읽고, 어떤 규칙이 있는지 파악하지 못하였다.
  • 언제 순간이동을 하고, 언제 점프를 해야 최소한의 에너지 소모로 도착이 가능할까..?
• 0부터 n까지의 거리로는 풀이법이 생각나지 않아, 역 순으로 생각했다.
• n부터 0까지 가는데, 잘 생각해보니 짝수일 때는 문제가 없지만 홀수일 때는 2로 나누면 소수가 나오니, 이런 경우엔 순간이동이 되지 않겠다는 생각이 들었다.
• 다시 말하면, 순간이동하는 경우의 도착점은 무조건 짝수 위치 라는 말이 된다.
• 입출력 예시를 다시 보니 n이 6일때는 순간이동해서 3으로 간다. 그리고 홀수 위치가 되면 점프를 하고, 다시 짝수가 되면 순간이동을 한다.
• 다시 확인해보려고 n이 5인 경우도 확인해보았다. 홀수일 때는 점프를 하고, 짝수일 때는 순간이동을 한다.
• 정리하자면, n에서 0으로 갈 때, 점프에 소모되는 에너지를 최소화하려면 가능할 때마다 무조건 순간이동을 해야한다는 말이 된다.
• 이게 가능하려면 짝수가 될 때마다 순간이동을 하고, 홀수일 경우엔 소수점이 나오므로 이때만 에너지를 1 소모하여 한 칸 점프하여 짝수로 만든다.

코드

function solution(n)
{
    // k칸 점프 : 건전지 k 소모
    // 순간이동 : 건전지 소모 X, 
    
    // 점프를(건전지 소모) 최소화하며 거리 n 도달하기, 이때 건전지 소모량 구하기
    // 현재 거리는 0
    // 1칸 일단 점프해서 이동 (순간이동은 * 2 인데, 0 * 2는 0 이므로)
    // 순간이동(곱하기 2)는 짝수 위치에만 도달 가능하다.
    let use = 0
 
    while(n > 0) {
        if(n % 2 === 0) {
            n = Math.floor(n / 2)
        } else {
            n -= 1
            use += 1
        }
    }
   
    return use
}