문제
문제 해설
이때까지 푼 문제 중 가장 시간이 오래걸린 문제입니다..
시간도 다른 문제와 달리 0.25초 안에 해결해야 하기 때문에 일반적인 bfs방식으로 풀면 풀리지 않습니다.
키 포인트는 수빈이가 도달할 수 있는 지점을 배열로 만들어 도달할 수 있는 최소 시간을 갱신하는 것인데, 갱신할 때 홀수인 시간과 짝수인 시간을 함께 곁들여야 합니다.
그리고 동생은 반드시 오른쪽으로 k+1, k+1+2, ... 이런식으로 움직이기 때문에 어디에서 출발하던 1000초 이후에는 500,000을 넘게 되어있습니다. 그래서 초기 도달 시간을 짝수는 1000, 홀수는 1001로 설정했습니다.
배열에 홀,짝을 함께 넣어야 하는 이유
오른쪽으로 갔다가 왼쪽으로 가는 경우를 생각해야 합니다. 그래서 만약 arrive[5][1] = 3 이면 5,7,9,... 과 같은 시간대는 수빈이가 도달할 수 있는 것입니다. 즉, 이 경우 3보다 큰 홀수 시간대에 동생이 방문하면 결국 만날 수 있습니다.
또, 수빈이가 도달한 시간보다 동생이 도달한 시간이 빠를 경우 만날 수 없기 때문에 최소 시간이 저장된 배열과 비교를 해야 합니다.
수빈이가 4에서 시작한다면, 8에 도달할 수 있는 시간은 1,4 입니다. 동생이 홀수 시간대에 들어왔다면 홀수 시간을 비교, 짝수 시간대에 들어왔다면 짝수 시간을 비교하고 동생보다 수빈이가 더 빨리 도착해야 성공입니다.
풀이 코드
from collections import deque
n, k = map(int, input().split())
# arrive[i][0] = 2
# arrive[i][1] = 5
# i에 수빈이가 도착하는 최소시간이 홀수는 3이고, 짝수는 5라는 뜻.
arrive = [[1000, 1001] for _ in range(500001)]
arrive[n][0] = 0
def bfs(n):
time = 0
q = deque()
q.append(n)
while q:
time += 1
size = len(q)
for i in range(size):
x = q.popleft()
is_odd = True if time % 2 == 1 else False
# 현재 시간이 홀수인 경우
if is_odd:
if 0 <= x - 1 <= 500000 and time < arrive[x - 1][1]:
# x-1이 홀수이고, x-1에 저장된 수 보다 빨리 도착할 경우
arrive[x - 1][1] = time
q.append(x - 1)
if 0 <= x + 1 <= 500000 and time < arrive[x + 1][1]:
arrive[x + 1][1] = time
q.append(x + 1)
if 0 <= 2 * x <= 500000 and time < arrive[2 * x][1]:
arrive[x * 2][1] = time
q.append(2 * x)
# 짝수의 경우
else:
if 0 <= x - 1 <= 500000 and time < arrive[x - 1][0]:
arrive[x - 1][0] = time
q.append(x - 1)
if 0 <= x + 1 <= 500000 and time < arrive[x + 1][0]:
arrive[x + 1][0] = time
q.append(x + 1)
if 0 <= 2 * x <= 500000 and time < arrive[2 * x][0]:
arrive[x * 2][0] = time
q.append(2 * x)
bfs(n)
answer = -1
time = 0
# 동생 움직이기
while k <= 500000:
# 홀,짝이 일치하고 수빈이가 먼저 지점에 도착할 수 있으면 성공
if time % 2 == 0 and arrive[k][0] <= time:
answer = time
break
if time % 2 == 1 and arrive[k][1] <= time:
answer = time
break
time += 1
k += time
print(answer)
