[PGM] 점프와 순간이동

문제링크

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

프로그래머스

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
Greedy

1. 문제 이해

점프는 K칸을 이동하는 것이고 순간이동은 지금까지 온 거리의 2배만큼 이동하는 것 입니다.

이 때 주의해야할 점은 점프는 배터리가 소모되고, 순간이동은 소모되지 않는다는 점입니다.

 

저는 이 문제를 처음에 대충 읽고 풀다가.. 뒤로도 점프하는 경우까지 고민했네요.(뒤로 점프가 가능하다면 예를들어 15로 가야할 경우에는 16에서 한칸 아래로 가면 2번만에 갈 수 있기 때문에 Greedy보다는 브루트포스로 해결해야합니다. 근데 제한사항을 보니 도저히 브루트포스로 해결할 수 없는 시간이어서 너무 고민했습니다. 문제를 잘 읽어야겠네요 ㅠㅠ)

뒤로 점프할 수 없으니 안심하시고 문제를 해결하시면 됩니다.

 

2. 접근방법

0에서부터 목표지점인 n까지 출발하는 것보다, n에서 돌아오는 방법을 사용하면 Greedy구현이 편리합니다.

연산은 나머지 연산을 사용해서 2의 배수인지 체크하여 주었습니다.

 

점프는 앞으로 갈 수 밖에 없으므로 목표지점인 n칸에서부터 2로 나누어지면 순간이동, 아니면 1칸 뒤로 이동하고 마지막에 점프한 횟수를 계산하면 간단하게 문제를 해결할 수 있습니다.

구현코드

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

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)