[BOJ][🟡3][백준#18235] 지금 만나러 갑니다

문제 출처

BAEKJOON Online Judge #18235

문제

여행을 마치고 꽉꽉나라로 돌아가던 중 오리와 육리는 서로를 잃어버렸다. 현재 오리는 점 A에 있고, 육리는 점 B에 있다. 오리와 육리는 서로를 찾기 위해 무조건 하루에 한 번씩 점프를 한다. 1일차에는 1만큼 점프하고 하루가 지날 때마다 서로가 더욱 보고 싶은 나머지 두 배씩 더 멀리 점프한다. 즉, 현재 위치가 X이고 서로를 찾기 시작한 지 y일차라면 점 X + 2y-1 또는 점 X - 2y-1로 점프한다. 0 이하의 점들과 N+1 이상의 점들은 디딜 땅이 없기 때문에 그곳으로 점프한다면 오리와 육리는 영원히 만나지 못한다. 아래 그림은 N = 10, A = 4, B = 10일 때의 예시이다. 화살표는 점프 가능한 위치를 나타낸다.

오리와 육리의 위치가 주어졌을 때, 둘이 만날 수 있는 최소 일수를 구해보자. 같은 날 같은 점의 땅에 도착했을 때 오리와 육리가 만난 것으로 간주한다.

입력

첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B)

출력

첫 번째 줄에 오리와 육리가 만날 수 있는 최소 일수를 출력한다. 만약 오리와 육리가 영원히 만날 수 없다면 -1을 출력한다.

예제

예제 1

입력

10 4 10

출력

2

예제 2

입력

2 1 2

출력

-1

예제 3

입력

7 2 6

출력

2

My Sol

def move(C):
    global n, day
    jump = 2**day
    new_C = set()
    for c in C:
        for op in (1, -1):
            if 0 < c+op*jump <= n:
                new_C.add(c+op*jump)
    return new_C

n, a, b = map(int, input().split())
A, B = {a}, {b}
day = 0
while True:
    if not (A and B):
        day = -1
        break

    A, B = move(A), move(B)
    day += 1
    if A & B: break

print(day)

set의 해시를 이용하면 굉장히 쉽게 풀 수 있는 문제였다. 시작점으로부터 1일차에는 1만큼, 2일차에는 2만큼… n일차에는 2**(n-1)만큼 이동하는 것을 이해한다.

1. 입력된 초기 위치를 A, B set에 각각 넣어준다.
2. 해당 위치부터 2**(n-1) step을 이동할 수 있는 경우의 수를 모두 set에 추가해준다.
3. set의 교집합을 활용해 어떠한 날에 A, B set이 일치하는 포인트가 있다면, 즉 어떠한 날에 같은 포인트에 도착할 수 있다면 while문을 종료한다.
4. 만약 날짜가 많이 지나 이동 거리가 너무 커지게 되면 특정한 날에 A, B 중 한 포인트도 범위 내에서 이동할 수 없다면 반복을 종료하고 -1을 출력한다.

결과

맞았습니다!!