수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.
예제 입력 1
5 17
예제 출력 1
2
처음 생각을 구현했을때는 모든 예제 입력을 맞았지만 메모리초과가 발생하였다.
처음 아이디어 (틀림)
import sys
sys.stdin=open('input.txt')
input=sys.stdin.readline
from collections import deque
LIMIT = 500_000
def in_range(a):
return 0<=a<=LIMIT
if __name__=="__main__":
N,K=map(int, input().split())
time=0
if N==K:
print(time)
sys.exit()
Q=deque()
Q.append((N,0))
while Q:
x,time=Q.popleft()
time+=1
NK = K + time*(time+1)//2
if not in_range(NK):
print(-1)
sys.exit()
for nx in [x-1, x+1, x*2]: # 3가지 경우를 다 돌아봄
if in_range(nx):
if nx==NK:
print(time)
sys.exit()
else:
Q.append((nx,time))
print(-1)
시간 제한이 0.25초로 빡빡하기 때문에 일반적인 방문체크로는 정답을 구할 수 없다. 이때 필요한 것이 짝수초와 홀수초로 나누어 방문 체크를 하는 것이다.
예를 들어 수빈이가 10의 위치에 2초에 도착했다고 가정해보자. 수빈이는 X-1이나 X+1을 이동할 수 있다. 즉, 10에서 왼쪽으로 한 번 이동하고 오른쪽으로 한 번 이동하는 방식으로 다시 같은 위치로 이동할 수 있다. 10의 위치에 2 + 2초, 2 + 4초, 2 + 6초, .... 와 같은 방식으로 도착할 수 있는 것이다. 만약 동생이 10의 위치에 6초가 걸려 도착했다면 둘은 6초에 10에서 만날 수 있음을 알 수 있다.
그렇기 때문에 방문 체크는 짝수초와 홀수초로 나누어 해당 위치에 짝수초에 도착했는지 홀수초에 도착했는지를 체크한다.
visited[loc][0] : loc 위치에 짝수초가 걸려 도착했음을 의미
visited[loc][1] : loc 위치에 홀수초가 걸려 도착했음을 의미
매 초마다 수빈이 방문할 수 있는 곳 체크
방문 한 적 없는 경우 현재 시간 저장. 현재 시간이 짝수인지 홀수인지에 따라 구분해서 저장(+1 -1로 다시 방문할 수 있기 때문에 최소시간만 저장)
수빈이가 이전에 이곳을 방문한 적이 있다면 동생 잡을 수 있는 것!
위와 같은 방법으로 방문 체크를 하면 시간 안에 수빈이와 동생이 몇 초에 만날 수 있는지를 구할 수 있다.
import sys
sys.stdin=open('input.txt')
input=sys.stdin.readline
from collections import deque
LIMIT = 500_000
def in_range(a):
return 0<=a<=LIMIT
if __name__=="__main__":
N,K=map(int, input().split())
# visited[loc][0] : loc 위치에 짝수초에 도착,
# visited[loc][1] : loc 위치에 홀수초에 도착
visited=[[-1,-1] for _ in range(LIMIT+1)]
time=0
# 시작부터 둘의 위치가 같을 경우 0 출력하고 종료
if N==K:
print(time)
sys.exit()
Q=deque()
Q.append(N)
time=1
K += time
while True:
if not in_range(K): # 동생이 500,000을 넘어서면 탐색 종료
break
nextQ=deque()
while Q: # 현재 시간에 가능한 경우의 위치
x=Q.popleft()
for nx in [x-1, x+1, x*2]: # 3가지 경우를 다 돌아봄
# 수빈이의 다음 위치가 범위 안에 있고 아직 도착한 적이 없는 위치라면
if in_range(nx) and visited[nx][time%2]==-1:
visited[nx][time%2]=time # 방문 체크를 해준다.
nextQ.append(nx) # 새로운 큐에 위치를 넣어주고
# 동생의 위치 K가 짝수초 또는 홀수초에 도착한 적이 있다면
# 현재 시간을 출력하고 시스템 종료
if visited[K][time%2] != -1:
print(time)
exit()
time+=1
K+=time
Q=nextQ
print(-1)
