점프와 순간 이동과 DP

1칸을 움직여 에너지를 1 소모할 것이냐, 거리가 조정되지 않지만 2배 위치로 순간 이동할 것이냐...

입출력 예시

N result
5 2

5칸을 움직이기 위해서 드는 최소 에너지

1칸 점프 (+1) (현재 위치: 1) -> 순간 이동 (현재 위치: 2) -> 순간 이동 (현재 위치: 4) -> 1칸 점프 끝!

우선 이 문제에서 중요한 부분은, 전체 문제를 부분 문제로 쪼갤 수 있다는 것. 그 말인즉슨 DP를 적용하면 된다는 것!

풀이

def solution(n):
    dp = [0] * (n+1)
    
    for i in range(1, n+1):
        dp[i] = dp[i-1] + 1
        
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2])
    
    return dp[n]

초기값을 다 0으로 설정하고, 일단 현재 칸에서 드는 에너지를 이전 칸에서 한 칸 점프했을 때의 에너지로 한다. 그 다음에 현재 칸의 인덱스가 짝수일 경우 이 칸은 순간이동으로도 올 수 있는 칸이므로 이전 칸에서 한 칸 점프했을 때의 에너지와 순간이동으로 올 수 있는 칸의 에너지 중 에너지가 더 적게 드는 방향으로 에너지 값을 넣으면 된다.

더 쉬운 풀이

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

그러나 출발점에서 시작하지 않고 도착점에서 출발점으로 오면 DP로 할 필요도 없이 문제를 더 쉽게 풀 수 있다...