문제 링크

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

문제 설명

• 0에서 N까지 이동할 때 사용되는 건전지 개수의 최솟값 리턴
  • 앞으로 한 칸 점프 : 건전지 1개
  • (현재까지 온 거리) x 2 로 순간 이동 : 건전지 0개

풀이

• 처음에 DP로 풀어봤는데 N이 최대 10억이어서 메모리, 시간 초과가 났다
• N이 홀수일 때만 1 빼주고, 카운트 1 하게 되면 logN에 가능할 것 같아 while 문으로 구현했다
• 예전에 자바로 푼 코드를 보니 이때는 재귀로 풀었던 것 같다

코드

def solution(n):
    count = 0
    while n > 0:
        # 홀수
        if n % 2:
            n -= 1
            count += 1
        # 짝수
        else:
            n = n // 2
    return count