[코딩테스트] 프로그래머스 점프와 순간 이동 파이썬(Python)

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

프로그래머스

def solution(n):
    result = 0
    while n:
        if n % 2 != 0:
            result +=1
            n -= 1
        else:
            n = n//2
    
    return result

 

문제에서 주어진 조건은 다음과 같습니다.

점프 : k칸 앞으로 점프, 

- k만큼의 건전지를 사용

순간이동 : 현재까지온 거리 x 2에 해당하는 위치로 이동

- 건전지 사용 없음

위의 조건으로 건전지 사용을 최소로하는 경우의 수 찾아야 합니다.

 

순간이동으로 많은 거리를 이동할 수 있고 건전지 사용이 없기 때문에 순간이동을 많이 사용하면서 순간이동을 사용하기 힘든 순간에는 건전지를 사용하여 점프를 해 순간이동을 할 수 있게 만들자는 아이디어로 문제를 해결했습니다.

 

먼저 주어진 n 에서 2로 나누면서 n이 0에 위치로 될때까지 반복을 합니다.

이때 n 이 홀수라면 순간이동이 힘들다고 판단하여 n에서 1을 빼주어 1칸 앞으로 점프를 하게 만들고 result변수에 1을 더하여 건전지를 1개 사용합니다.

- 순간이동을 했을 때 이동한 위치가 자연수가 아니라면 순간이동이 힘들다고 판단했습니다.

n이 짝수라면 순간이동을 쉽게 할 수 있기 때문에 n을 2로 나누어 줍니다.

 

반복문이 종료가 되면 건전지 사용량(result)를 return 합니다.