백준 17071 숨바꼭질 5

동생과 언니가 어느 한 지점에 둘다 짝수번 또는 홀수번만에 도착하면 언니는 +1 과 -1을 반복(원점으로 돌아가길 반복)해서 동생과 만날 수 있다.
조건 . 언니가 동생보다 만날 지점에 빠른 시간에 도착해야함
ex) 테스트케이스 1번에서
15에서 최종적으로 둘이 만나면 언니는 2초만에, 동생은 4초만에 15에 도착해야 언니가
15+1 -> 15+1-1 해서 4초에 15로 간다.

from collections import deque

n, k = map(int, input().split())
check = [[-1] * 500001 for _ in range(2)]
dist = [-1] * 500001
i = 0
while k <= 500000:
    dist[k] = i
    i += 1
    k += i
q = deque()
q.append(n)
check[0][n] = 0
while q:
    x = q.popleft()
    for y in [x - 1, x + 1, 2 * x]:
        if y > 500000 or y < 0: // 1번
            continue
        if check[1][x] != -1 and check[0][y] == -1:
            check[0][y] = check[1][x] + 1
            q.append(y)
        if check[0][x] != -1 and check[1][y] == -1:
            check[1][y] = check[0][x] + 1
            q.append(y)
ans = -1            
for i in range(500001):
    if dist[i] == -1:
        continue
    if dist[i] % 2 == 0 and check[0][i] != -1:
        if dist[i] >= check[0][i]: //2번
            ans = dist[i]
            break
    elif dist[i] % 2 != 0 and check[1][i] != -1:
        if dist[i] >= check[1][i]:
            ans = dist[i]
            break
        
print(ans)

언니가 이동하는 배열 check, 동생이 이동하는 배열 dist를 만들었다.
check는 짝수시간, 홀수시간 나눠서 이동하기 위해 2차원배열로 만들어줬다.
답(ans)를 구할 때는 위의 조건을 반영해야한다.

💡 1번 : x-1로도 이동할 수 있어서 음수가 될 수 있는데 y < 0를 따지지 않아서 만약 n 이 1이 들어가면 에러가 난다.
💡 2번 : 조건을 따져서 했어야하는데 안따져서 답이 안구해졌었다.

from collections import deque

n, k = map(int, input().split())
check = [[-1] * 500001 for _ in range(2)]

q = deque()
q.append(n)
check[0][n] = 0

while q:
    x = q.popleft()
    for y in [x - 1, x + 1, 2 * x]:
        if 0 <= y <= 500000:
            if check[1][x] != -1 and check[0][y] == -1:
                check[0][y] = check[1][x] + 1
                q.append(y)
            if check[0][x] != -1 and check[1][y] == -1:
                check[1][y] = check[0][x] + 1
                q.append(y)
                
t = 0
ans = -1
while k < 500001:
    if t >= check[t % 2][k]:
        ans = t
        break
    t += 1
    k += t
print(ans)

동생의 배열을 따로 만들지 않고 해결
동생과 언니가 만나는 시간을 t라고 놓고 구한다.

t = 0
ans = -1
while k <= 500000:
    k += t
    if t >= check[t % 2][k]:
        ans = t
        break
    t += 1
print(ans)

처음에 마지막 정답 구하는 부분을 이런 식으로 짰는데 이럴 경우 k 가 500000 일 때 범위 초과가 일어나서 에러가 난다.

from collections import deque

n, k = map(int, input().split())
check = [[-1] * 500001 for _ in range(2)]

q = deque()
q.append((n, 0))
check[0][n] = 0

while q:
    x, u = q.popleft()
    for y in [x - 1, x + 1, 2 * x]:
        if 0 <= y <= 500000:
            if check[1 - u][y] == -1:
                check[1 - u][y] = check[u][x] + 1
                q.append((y, 1-u))
                
t = 0
ans = -1
while k < 500001:
    if t >= check[t % 2][k]:
        ans = t
        break
    t += 1
    k += t
print(ans)

큐에 시간까지 넣어서 더 간단하게 만들 수 있다. 시간이 홀수인지 짝수인지 이미 판별이 끝났기 때문에 check[1][x] != -1 와 check[0][x] != -1 은 판별해 줄 필요 없다