문제 링크

• https://www.acmicpc.net/problem/1697

문제 설명

• n, k가 주어짐
• +1, -1, *2로 n에서 k까지 도달하는 최소 연산 횟수 출력

풀이

• n에서 시작해 BFS로 k까지 탐색
• n, k의 범위가 0~100000이라 범위를 리스트 길이를 0~200000으로 초기화했다

느낀 점

• 처음에는 DP를 생각해서 벨만-포드 느낌으로 풀어보려 했는데 시간 초과
• 노드 별 거리가 1이라 BFS로 해야하는 것 같다

코드

from collections import deque

def bfs():
    visited = [False] * 200001
    visited[n] = True
    dist = [0] * 200001
    q = deque([n])
    while q:
        cn = q.popleft()
        if cn == k:
            return dist[cn]
        for i in range(3):
            nn = get_next_num(cn, i)
            if 0 <= nn < 200001:
                if not visited[nn]:
                    visited[nn] = True
                    q.append(nn)
                    dist[nn] = dist[cn] + 1


def get_next_num(num, i):
    if i==0:
        return num-1
    if i==1:
        return num+1
    return num * 2


n, k = map(int, input().split())
print(bfs())