Baekjoon-14226-이모티콘

from collections import deque
S = int(input())
N = 1001

# BFS (DP를 써볼까도 했지만 Time complexity는 거의 동일하다)
queue = deque([[1,0]]) # 화면, 클립보드
visited = [[-1 for _ in range(N)] for _ in range(N)]
visited[1][0] = 0

while queue:
    monitor, clipboard = queue.popleft()
    children = []
    children = [(monitor,monitor)]
    if clipboard != 0 and monitor+clipboard < N:
        children += [(monitor+clipboard, clipboard)]
    if monitor > 0:
        children += [(monitor-1, clipboard)]

    for m,c in children:
        if visited[m][c] == -1:
            visited[m][c] = visited[monitor][clipboard] + 1
            queue.append((m,c))

print(min([s for s in visited[S] if s != -1]))

from collections import deque
S = int(input())
N = 1001

# BFS (DP를 써볼까도 했지만 Time complexity는 거의 동일하다)
queue = deque([[1,0]]) # 화면, 클립보드
visited = dict()
visited[(1,0)] = 0

while queue:
    monitor, clipboard = queue.popleft()
    if monitor == S:
        print(visited[(monitor,clipboard)])
        exit()
    
    children = []
    children = [(monitor,monitor)]
    if clipboard != 0 and monitor+clipboard < N:
        children += [(monitor+clipboard, clipboard)]
    if monitor > 0:
        children += [(monitor-1, clipboard)]

    for m,c in children:
        if (m,c) not in visited.keys():
            visited[(m,c)] = visited[(monitor,clipboard)] + 1
            queue.append((m,c))