[SW Expert Academy] 5247. 연산

5247. 연산

---

문제)

 

자연수 N에 몇 번의 연산을 통해 다른 자연수 M을 만들려고 한다.

사용할 수 있는 연산이 +1, -1, *2, -10 네 가지라고 할 때 최소 몇 번의 연산을 거쳐야 하는지 알아내는 프로그램을 만드시오.

단, 연산의 중간 결과도 항상 백만 이하의 자연수여야 한다.

예를 들어 N=2, M=7인 경우, (2+1) *2 +1 = 7이므로 최소 3번의 연산이 필요한다.

 

[입력]

첫 줄에 테스트 케이스의 개수가 주어지고, 다음 줄부터 테스트 케이스 별로 첫 줄에 N과 M이 주어진다. 1<=N, M<=1,000,000, N!=M

 

 

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

 

 

풀이)

 

from collections import deque
 
def bfs(a):
    queue = deque()
    queue.append(a)
    visited[a] = 1
    d = 0
    while queue:
        # 각 레벨의 수를 카운트 해주고, 그 카운트가 넘어갈 때마다
        # 연산의 카운트를 1씩 늘려준다.
        size = len(queue)
        for _ in range(size):
            a = queue.popleft()
 
            if a == m:
                return d
 
            # 의도치 않은 하드코딩..
            if 0 < a + 1 < 1000001 and not visited[a + 1]:
                queue.append(a + 1)
                visited[a + 1] = 1
            if 0 < a - 1 < 1000001 and not visited[a - 1]:
                queue.append(a - 1)
                visited[a - 1] = 1
            if 0 < a * 2 < 1000001 and not visited[a * 2]:
                queue.append(a * 2)
                visited[a * 2] = 1
            if 0 < a - 10 < 1000001 and not visited[a - 10]:
                queue.append(a - 10)
                visited[a - 10] = 1
        d += 1
 
 
T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    # null null하게 200만까지 만들어주었다.
    visited = [0] * 2000010
    print(f"#{_ + 1} {bfs(n)}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.