연산 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 5247

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

자연수 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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 2 7 3 15 36 1007	#1 3 #2 4 #3 8

---

2. 문제풀이

특정수가 있으면 거기에 4가지 경우를 추가하여 모든 경우를 탐색했다. 범위가 상당히 크기때문에 가지치기를 하지 않는다면 터지게 된다. 예를들어서 2에서 +1을 해서 3이 추가 되었는데 3에서 -1을하면 2가 되고 아까와 같이 쓸데없는 연산이 계속 추가되게 된다. 따라서 해당 수를 사용했다고 체크를하는 변수를 하나 만들어줘 중복을 방지했다. 또한 1보다크고 1,000,000보다 작아야 하므로 계산해서 넘기기전에 범위에 들어가있는지 체크를 한다. 이 과정을 반복하다가 원하는 결과가 나오게된다면 bfs이므로 바로 지금까지 count한 값을 리턴해준다.

---

3. 소스코드

#D4 5247 연산
from collections import deque
 
def bfs(N, M):
    queue = deque()
    queue.append((N, 0))
    check = {}
    while queue:
        item, count = queue.popleft()
        if check.get(item, 0): continue
        check[item] = 1
        if item == M: return count
        count += 1
        if 0 < item+1 <= 1000000:
            queue.append((item+1, count))
        if 0 < item-1 <= 1000000:
            queue.append((item-1, count))
        if 0 < item*2 <= 1000000:
            queue.append((item*2, count))
        if 0 < item-10 <= 1000000:
            queue.append((item-10, count))
 
for t in range(int(input())):
    N,M = map(int, input().split())
    print('#{} {}'.format(t+1, bfs(N,M)))