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

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

📌  문제 접근

N번째 칸까지 가면서 순간이동 또는 점프를 이용할 수 있다.

점프는 이동한만큼 건전지 사용량이 증가하고, 순간이동은 현재까지 이동한 칸수*2의 위치에 도달한다.

문제를 읽으면서 DP를 이용하면 된다고 생각했다.

 

🧐 첫 번째 풀이: DP (실패)

너무나 당연하게 통과할 줄 알았는데 시간초과가 났다 ㅠㅠ

def solution(n):
    dp = [float('inf')]*(n+1)
    dp[0] = 0
    for i in range(n):
        # 점프
        dp[i+1] = min(dp[i]+1, dp[i+1])
        # 순간이동
        if 0<i*2<=n:
            dp[i*2] = min(dp[i*2], dp[i])
    
    return dp[n]

 

제한 사항을 다시 봤는데

숫자 N: 1 이상 10억 이하의 자연수

제한이 엄청 컸다..

 

😃 두 번째 풀이: 2로 나누기 (성공)

이번에는 0에서 이동할 수 있는 칸으로 가는 게 아니라 N번째 칸에서 0으로 가는 방식을 생각했다.

N이 짝수이면 $N/2$ 번 칸에서 순간이동으로 오는 것이 가장 효율적이니까 2로 나눠주고

홀수이면 순간이동으로 올 수 없으니 1칸을 줄이며 건전지 사용량을 늘렸다.

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