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

문제

프로그래머스 Summer/Winter Coding(~2018)

• Lv 2. 점프와 순간 이동 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/12980

코드 구현

def solution(n):
    ans = 1  # 0에서 1은 무조건 점프 한번 해야하므로 1은 더해놓고 시작

    # 점프는 최소화, 순간이동은 현재위치 * 2로 이동
    # 최소 건전지 사용량 리턴하기

    while (n > 1):
        if (n % 2 != 0):  # 홀수면 -> 점프로 1칸 이동
            ans += 1
            n -= 1
        n = n // 2  # 2로 계속 나눠주면서 이동

    return ans

풀이

• 홀수인가 짝수인가에 따라서 점프와 순간이동을 적절히 섞어야 한다.
• 점프를 최소화해야 하지만 우선 0에서 시작하면 순간이동은 하지 못하니 1로 점프는 필수적으로 해야한다. → 따라서 ans = 1로 하나 더하고 시작
• 0부터 시작해서 n까지 따지기 보다는 n에서 내려가는 방식으로 따진다.
  • 만약 현재 홀수라면 → 이동하기 이전 숫자에서 2를 곱해서(순간이동) 홀수로 올 수 없으므로 점프로밖에 못온다. → ans += 1 → 점프로 온걸 하나 빼준다 n -= 1
    • ex) 0 1 2 3 4 5
    • 5 → 1부터 4까지 2를 곱해서 5가 되는 방법은 X → 점프로 5를 온 것 → 4에서 점프하는게 최소 (1칸 점프)
  • 2로 계속 나눠주면서 1에 도착할 때까지 이동한다.