[프로그래머스] 점프와 순간 이동

이번 문제는 문제 설명 길이에 비해 너무너무 쉬운 문제라서 바로 풀었습니다.

---

접근방법

n=5

처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

• 0->1 점프 : 건전지 사용량 1
• 1->2 (현재까지 온 거리 : 1) x 2 순간이동
• 2->4 (현재까지 온 거리 : 2) x 2 순간이동
• 4->5 점프 : 건전지 사용량 2

n=6

처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치 3으로 이동합니다. 이때 다시 순간이동하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.

• 0->1 점프 : 건전지 사용량 1
• 1->2 (현재까지 온 거리 : 1) x 2 순간이동
• 2->3 점프 : 건전지 사용량 2
• 3->6 (현재까지 온 거리 : 3) x 2 순간이동

n=5, n=6일때 푸는 과정을 보면서 n이 짝수이면 *2, 홀수이면 +1을 해주는 규칙성을 발견했고,

이 점을 활용해서 반대로 n이 짝수이면 /2, 홀수이면 -1을 해주었습니다.

 

n=5000

• 5000/2 = 2500
• 2500/2 = 1250
• 1250/2 = 625
• 625-1 = 624
• 624/2 = 312
• 312/2 = 156
• 156/2 = 78
• 78/2 = 39
• 39-1 = 38
• 38/2 = 19
• 19-1 = 18
• 18/2 = 9
• 9-1 = 8
• 8/2 = 4
• 4/2 = 2
• 2/2 = 1
• 1-1 = 0

건전지 사용량 : 5

---

해결방안

function solution(n)
{
    var ans = 0;
    while(n!==0){
        if(n%2 === 1){
            n--;
            ans++;
        }else n/=2;
    }
    return ans;
}

while문을 이용해서 n이 0이 될 때까지 반복해주었습니다.

n%2가 1이 나오면 n-1을 해주고 ans+1을 해주었고

n%2가 0이 나오면 n/2을 해주었습니다.

---

여기까지 프로그래머스 점프와 순간 이동 해결방안에 대해 설명해보았습니다.