실버 I

💡문제 분석 요약

BFS or math

💡알고리즘 설계

queue에 n값을 추가한 뒤, k값이 될 수 있는 방법을 각각 넣어서 확인한다.

이때, 재방문하지않도록 visit이라는 배열로 방문 여부를 확인한다.

💡코드

from collections import deque
n,k = map(int,input().strip().split())
queue = deque()
queue.append(n)
answer =0
visit = [False for _ in range(100001)]
while queue:
    new = deque()
    for i in range(len(queue)):
        n = queue.popleft()
        if n==k:
            break;
        visit[n] = True
        for i in [n*2,n+1,n-1]:
            if 0<=i<100001 and not visit[i]:
                new.append(i)
    if n == k:
        break;
    queue = new
    answer += 1
print(answer)

💡시간복잡도

i의 N과 j 의 N O(n^2)

💡 다른 코드

복잡하게 풀지 않고 수학적으로 풀 수 있다.

def solution(N,K):
    if K <= N: return N-K
    elif K == 1: return 1
    elif K % 2 == 0: return min(K-N,solution(N,K//2)+1)
    else: return min(solution(N,K+1)+1, solution(N,K-1)+1)
 