[Programmers / Level2] 점프와 순간이동

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

프로그래머스

---

<내 코드>

def solution(n):
    cnt = 0
    while True:
        if n == 0: return cnt
        elif n % 2 == 1: 
            n = n - 1
            cnt += 1
        else: n = n // 2

 

-> 맞게 접근한 것 같은데 결을 못 맺어서 아쉽다. 짝/홀 에 대한 판단은 섰었는데 그리디한방법을 bottom-up으로 접근해서 많이 해맸다.

채찍선생님은 아래와 같이 dp로도 풀 수 있다고 말씀하신다.

 

<정해코드 - GPT>

def solution(N):
    dp = [0] * (N + 1)

    for i in range(2, N + 1):
        # 점프를 사용하는 경우
        jump = dp[i - 1] + 1
        # 순간이동을 사용하는 경우 (이전 위치의 건전지 사용량)
        teleport = dp[i // 2] if i % 2 == 0 else float('inf')

        dp[i] = min(jump, teleport)

    return dp[N]

 

-> dp는 bottom-up으로 접근하여 jump 또는 teleport하는 최적의 상황을 dp테이블에 꽂아 넣었다. 10억이상 넘어가면 곤란해진다.