풀이_16953.md

🗽 백준 16953 (A->B)

• Date : 2021.05.23(일)
• Time : 30분

문제

• 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.

  A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

• 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

• A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
  
  

풀이

def findCount(a):
    visited = []

    myQ = deque()
    myQ.append([0,a])
    visited.append(a)

    while myQ:
        count, num = myQ.popleft()

        if num == b:
            return count + 1

        for next in (num * 2, int(str(num) + "1")):
            if next <= b:
                if next not in visited:
                    myQ.append([count + 1, next])
                    visited.append(next)

    return -1

: bfs를 이용해 두가지 방법에 대한 모든 경우의 수를 체크해주면 된다. deque에는 [연산횟수,현재숫자]가 들어간다. 그래서 만약 현재 숫자가 마지막 숫자에 도달했다면 count+1를 해서 return 하면 된다. 만약 아직 도달하지 않았고 중간에 들리는 숫자가 들리지 않은 숫자라면 그 숫자가 다음 숫자가 되고, 들렸다는 표시를 하기위해 visited에 저장해준다. bfs는 난 어려워..