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

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

프로그래머스

---

문제를 보자마자 너무 dp문제같아서 dp 로 풀었는데,

정확성 테스트는 모두 성공했지만, 효율성 테스트에서 전부 다 시간초과가 떴다.

 

처음 제출한 코드는 이렇다.

 python

def solution(n):
    INF = int(1e9)
    dp = [INF for _ in range(n+1)]
    
    dp[0] = 0
    dp[1] = 1
    
    for i in range(1,n+1):
        dp[i] = min(dp[i], dp[i-1]+1)
        if i*2 < n+1: # 순간이동이 가능하다면 순간이동
            if i*2 == n:
                return dp[i]
            dp[i*2] = dp[i]
            
    return dp[n]

위 코드는 빅오시간이 O(n)이기 때문에 시간 복잡도가 더 좋은 코드를 새로 짜야겠다고 느꼈다.

즉 모든 i값을 하나하나 확인해가며 건전지 소모량을 계산하는 풀이를 사용하면 안 된다.

 

다른 풀이를 참고하여 O(logn) 시간복잡도를 갖는 코드를 새로 작성했다

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