import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
start, finish = map(int, input().split())
explored = set()
q1 = deque([start])
def bfs(q1: deque, time_lapse: int):
q2: deque = deque()
while q1:
v = q1.popleft()
if v == finish:
print(time_lapse)
return
if v not in explored:
explored.add(v)
for i in [v+1, v-1, v*2]:
if i >= 0 and i <= 100000:
q2.append(i)
bfs(q2, time_lapse+1)
bfs(q1, 0)
메모리: 136492 KB, 시간: 388 ms
deque
를 사용했다.[v+1, v-1, v*2]
)에 대해 범위를 벗어나지 않는지 확인하며 두번째 큐에 추가한다.time_lapse
를 bfs
함수에 되먹여 호출해 재귀한다.finish
가 큐에서 나올 때 시간이 얼마나 지났는지 time_lapse
를 출력하고 종료한다.크게 어렵지 않은 로직이다. 문제 그대로 풀어 구현할 수 있는 코드이다. 다만 마지막 for
반복문에서 i
의 범위를 지정해주지 못해 메모리 초과 에러로 고생했다. 아래 코드에 비해 시간, 공간복잡도가 크다. 아래 코드보다 재귀의 깊이도 훨씬 깊다.
import sys
def f(n, k):
if n >= k:
return n - k
if k == 1:
return 1
if k % 2:
return min(f(n, k+1), f(n, k-1)) + 1
return min(k-n, f(n,k//2)+1)
print(f(*map(int,sys.stdin.readline().split())))
메모리 약 31MB, 시간 36ms
n
이 k
보다 같거나 크면 n - k
를 반환한다. 움직이지 않아도 되거나 뒤로 한칸씩 가는 수밖에 없기 때문이다.k
가 1이라면 1을 반환한다. 1번 경우를 제외하면 n
이 0인 경우밖에 없다. 0에서 1로 가는 경우이므로 1을 반환. 3, 4번 조건으로 처리하지 못하는 경우다?k
가 2로 나누어 떨어지지 않는다면, k
의 주변값에 대해 재귀하고, 둘 중 더 작은 값에 1을 더하여 반환한다. k
에서 한걸음 떨어진 값이기 때문이다.k-n
과 k
를 2로 나눈 값을 되먹인 함수 + 1 중 더 작은 값을 반환한다.*2
)을 한번 했다는 뜻이다.k-n
: n
에서 k
로 한 걸음씩 왔다는 뜻. 순간이동 한 것보다 이 값이 더 작으면 이 값을 반환한다. 왜 이 값인가? k
가 2로 나누어 떨어질 때, 한 걸음씩 가는 방법과 그것을 2로 나눈 값에 한 걸음씩 가는 방법이 있다. 여기서 k
는 k//2
로 되먹여지고 그 주변 값에 대해 3번을 수행하거나 다시 4번을 수행하게 될 것이다. 그 값이 f(n,k//2)
로 반환되는데 한 번 순간이동을 했으니 1을 더한다. n
과 k//2
에 대해서도 반복 수행. f(n, k//2)
함수가 호출되었을 때 k//2
가 2로 또다시 나누어 떨어진다면 나눌 때마다 1씩 더해진 값이 반환될 것이며, k//2
가 2로 나누어 떨어지지 않는 순간에 대해서 k-n
이 반환될 것이다.k = 10
, n = 2
인 경우, 처음 f(2, 10)
가 실행되고 4번 케이스에서 f(2, 5)
가 실행된다. 5
는 홀수이므로 3번 케이스 진입, k
가 4 또는 6인 경우에 대해 실행하는데, f(2, 4)
는 1이고 (f(2, 2) + 1
) f(2, 6)
은 2이다 (f(2, 3) + 1
). f(2, 5) = f(2, 4) + 1 = 2
, f(2, 10) = f(2, 5) + 1 = 3
이 된다.다이나믹 프로그램으로 풀 수 있을 것 같다는 생각이 들었지만 구현하지 못했다. 그만큼 아직 다이나믹 프로그래밍이 익숙하지 않다는 뜻일 것이다. 많이 연습해야겠다.