[알고리즘] 프로그래머스 - 점프와 순간 이동

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

시간초과 난 내 풀이1

from collections import deque
from collections import defaultdict

def bfs(cur, n):
    q = deque()
    q.append((cur, 0))
    move_dict = defaultdict(int)
    while q:
        pos, count = q.popleft()
        if pos == n:
            return count
        if pos * 2 not in move_dict.keys() or move_dict[pos*2] > count:
            move_dict[pos*2] = count
            q.append((pos*2, count))
        if pos + 1 not in move_dict.keys() or move_dict[pos+1] > count:
            move_dict[pos+1] = count + 1
            q.append((pos+1, count+1))

def solution(n):
    cur = 0
    return bfs(cur, n)

시간 초과 난 내 풀이 2

from collections import defaultdict

def solution(n):
    dp = defaultdict(int) # dp[i]는 i까지 이동하는데 드는 배터리. 기본적으로 한칸씩 이동하면 i씩 든다
    for i in range(1, n+1):
        if i % 2 == 0:
            dp[i] = min(i, dp[i-1]+1, dp[i//2])
        else:
            dp[i] = min(i, dp[i-1]+1)
    return dp[n]

다른 사람 풀이

def solution(n):
    cnt = 0
    while n:
        q, r = divmod(n, 2)
        n = q
        if r != 0:
            cnt += 1
    return cnt

역으로 현재위치에서 0까지 도달하는데 얼마나 걸리나 계산하면 된다.

출처: https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%EC%A0%90%ED%94%84%EC%99%80-%EC%88%9C%EA%B0%84-%EC%9D%B4%EB%8F%99

만약 뒤로 돌아가는 것까지 고려했으면 bfs나 dp를 썼어야했다.