프로그래머스 - 점프와 순간 이동 (Summer/Winter Coding(~2018)) [Python]

 

 문제

 

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

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

 

 

 

 

 

 

 

 

 문제 상황

 

- 연료를 사용하여 점프를 하거나, 연료 사용없이 지금까지 이동해온 거리만큼 순간이동을 하여 움직이는데 목표점을 정확히 도착하는데 최소의 연료로 도착할 때 연료 소비량을 계산한다.

 

 

 

 

 

 

 

 

 해결 전략

 

- 최대한 2배가 되는 것을 활용해야 하고 점프를 최소화 해야한다. 역으로 생각하여 2배로 이동하는 것을 최대로 활용하기 위해 주어진 n을 2로 나누면서 홀수일 경우 1을 빼주고 fuel을 1 더해준다. 이 때가 한칸 점프하는 시점이다. 짝수일 때에는 그냥 2로 나눠주고 이 때는 연료 소비가 없다. 

 

 

 

 

 

 

 코드

 

def solution(n: int) -> int:
    fuel = 1
    while n > 1:
        if n % 2 == 1:
            fuel += 1
            n -= 1
            continue
        n //= 2
    return fuel
 

 

 

 

 

 

 

 

 

 해설

 

- 해결 전략 그대로이다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 아이디어가 불현듯 떠오름. 문제의 조건을 역으로 실행하는 것을 항상 염두해두자.