[BOJ 17619, Python 3] 개구리 점프

https://www.acmicpc.net/problem/17619

17619번: 개구리 점프

 

 

풀이

문제 본문에서 수직으로 점프할 때, 통나무와 통나무 사이에 통나무가 있으면 점프를 못한다고 나와있습니다.

근데 이건 생각해보면 통나무 -> 통나무 -> 통나무로 이동하면 되는 것이라서 통나무와 통나무 사이에 통나무가 있어도 상관이 없다는 것을 캐치했으면 문제가 매우 쉬워집니다.

 

어떻게 되든 x값의 범위만 겹치면 어떻게든 이동할 수 있어서 사실상 y축이 상관이 없는거죠

 

이제 y축 값이 상관 없다는 것을 알았으니 문제는 선 긋기 문제로 치환될 수 있습니다. 선 긋기 문제랑 살짝 다른 점은 길이를 구하는 것이 아니라 a번째 통나무와 b번째 통나무가 같은 선분에 속하냐를 확인하는 것이죠

 

이건 알아서 짜면 되는데 저 같은 경우엔 통나무 구간 값을 입력 받을 때 인덱스까지 추가하고, x_1값을 기준으로 오름차순으로 정렬하였습니다.

 

 

정렬하면 위 사진처럼 통나무가 정렬되고, 각 통나무들은 인덱스 값을 가지고 있으니 선분의 오른쪽 좌표를 업데이트하며 구간이 겹치는 통나무들은 전부 같은 번호에 저장하고, (선분의 오른쪽 좌표) < (새로운 통나무의 왼쪽 좌표)가 되면 새로운 번호에 저장하면 됩니다.

위 사진을 예시로 들자면 1번째 ~ 5번째 통나무는 1번에 저장하고, 6번째 통나무는 2번, 7번째 통나무는 3번에 저장하는 것이죠

이렇게 처리를 해주면 O(1)로 답을 출력할 수 있습니다.

 

 

코드

input = __import__('sys').stdin.readline
n, q = map(int, input().split())
arr = sorted([[*map(int, input().split())] + [i] for i in range(n)])
p = [i for i in range(n)]
val = arr[0][1]
idx = arr[0][3]
for i in range(1, n):
    if arr[i][0] <= val:
        val = max(val, arr[i][1])
        p[arr[i][3]] = idx
    else:
        val = arr[i][1]
        idx = arr[i][3]
for i in range(q):
    x, y = map(int, input().split())
    if p[x-1] == p[y-1]: print(1)
    else: print(0)