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

 

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

코딩테스트 연습 - 점프와 순간 이동

 

Greedy하게 접근하면 쉽게 풀 수 있는 문제입니다.

 

아래 풀이의 주석에서 설명한 것처럼 (짝수번 째 칸 * 2)한 지점까지의 에너지 소모량은 0이고, 홀수 칸에서 짝수칸을 가기 위해서는 +1을 점프해주면 되기 때문에 이를 역으로 구현해주었습니다.

 

ps. 처음에는 DP라고 생각해서 풀었는데, 정답은 맞지만 n이 1억 이하의 범위라서 DP 배열의 메모리 초과로 인한 런타임 에러가 납니다!

def solution(n):
    answer = 0

    # Greedy -> n부터 시작해서 짝수는 무조건 그 절반에서 순간이동
    # 홀수일때는 그 전 칸이 짝수칸 이므로 +1만 점프
    while n >= 1:
        if n % 2 == 0:
            n //= 2
        else:
            answer += 1
            n -= 1
    return answer