[이분법] 프로그래머스 lv2. 점프와 순간이동

문제

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

 

---

설계 ✨

순간이동은 건전지가 사용되지 않지만, 현재까지 온 거리 * 2에 해당하는 위치로 순간이동해야하고,  k칸 앞으로 점프하는 것은 건전지가 k만큼 사용된다고 한다. 즉, 이 문제는 최대한 순간이동을 사용해서 얼만큼 점프했는지 알아보는 문제이다.

 

1. 0부터 주어진 거리를 수직선을 그려놓고 설계했다. 

 

2. 주어진 거리에 있는 곳까지 딱 도착해야하므로 뒤에서부터 생각해보았다.

 

3. 주어진 거리에서 2로 나누어 떨어지면 점프없이 바로 그 위치로 순간이동을 할 수 있고, 주어진 거리에서 2로 나누어 떨어지지 않으면 2로 나눈 나머지만큼은 점프해야하고, 2로 나눈 몫만큼은 순간이동을 할 수 있다. 

 

4. 출발점에서 최소 한칸을 점프를 해야 현재까지 온 거리가 1이상이 되어서 *2를 했을 때 거리가 계산되므로 순간이동을 할 수 있다. 

출발점에서 바로 순간이동을 할려고 하면 현재까지 온 거리가 0이기 때문에 순간이동이 불가능하다는 점이 유의깊게 볼 점이다. 

 

5. 그렇기 때문에 1이 될때까지 반복하고, 반복문이 끝나면 점프 카운트를 1을 추가해줬다. 

 

 

 

이 문제는 27분안에 풀었고, 어떤 알고리즘을 쓰는게 좋을지 생각하면 쉬운 문제였다. 

 

 

def solution(n):
    ans = 0
    point = n 
    while point > 1 : 
        if point % 2 == 0:
            point = point // 2
        else:
            ans += point % 2 
            point = point // 2
    ans += 1  

    return ans