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

문제 링크

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

프로그래머스

 

문제 설명

아이언 슈트는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있다.

아이언 슈트는 건전지로 작동하는데, 순간이동을 하면 건전지 사용량이 줄지 않지만,

앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 든다. 건전지 사용량을 줄이기 위해 점프로 이동하는 것을 최소화 하려고 한다. 이동 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 문제이다.

제한 사항

• 숫자 N : 1 이상 10억 이하의 자연수
• 숫자 K : 1 이상의 자연수

 

풀이

순간이동을 최대한 많이 이용해서 건전지 사용량을 최소화해야 한다.

방식을 잘 찾아보면 N가 짝수 일 때는, N / 2 위치에서 순간이동을 하면 건전지를 사용하지 않아도 된다.

반대로 홀수 일 때, N - 1(점프)을 하여 짝수로 만든 다음, 순간이동을 할 수 있게 만들어 준다면 건전지 사용량을 최소화할 수 있다. 

 

✅ Code - 성공

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

    return ans