프로그래머스: 점프와 순간이동 (파이썬, 구현)

간단한 구현문제이다. 최소값을 구하는 문제이기에 완전탐색, DP, 구현 세가지 방법이 떠올랐으나 제한 사항을 보고 바로 구현문제임을 알 수 있었다.

왜냐하면 N이 10억 이하의 자연수로 일반적으로 효율성 테스트를 통과하기 위해서는 1초안에 통과해야 하는데 1초안에 통과하기 위해선 시간복잡도가 1억 이하여야 하기 때문이다.

 

문제의 조건을 우선 보면 지나온 거리에 2를 곱하여 이동하는 순간이동은 count를 올리지 않고 1씩 이동하는 것만 count를 올리므로 N이 짝수라면 2로 나누고 N이 홀수라면 1을 빼주어 짝수로 만들어 다시 2로 나누는 작업을 N이 1이 될 때까지 반복하면 됨을 알 수 있다.

 

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