17619. 개구리 점프

1개월 반만에 백준 문제를 풀어 보았다.

17619번: 개구리 점프

---

조건을 자세히 읽어 보면, 다음을 관찰할 수 있다.

 

1. 점프할 때 다른 통나무를 건너뛸 수 없다고 적혀 있지만, 건너뛰는 통나무에 내렸다가 가면 되기 때문에 의미없는 조건이다.

따라서 세로 좌표는 의미가 없고, 가로로만 겹쳐 있으면 이동할 수 있다고 간주해도 좋다. 

 

2. 두 통나무 $A$와 $B$($A.x_{1} \le B.x_{1}$)가 있을 때, $A$와 $B$가 가로로 겹칠 조건은 $B.x_{1} \le A.x_{2}$이다.

 

3. $A$와 $B$가 겹친다면, $A$와 $B$를 하나의 통나무로 간주해도 된다. 앞서 말했듯이 $y$는 의미가 없기 때문.

 

 

1, 2, 3을 조합하여 문제를 해결해 보자.

 

우선 통나무를 $x_{1}$의 오름차순으로 정렬한 후(정렬할 때 $y$는 신경쓰지 않아도 된다), 앞에서부터 자신과 겹치는 통나무를 같은 그룹으로 합친다. 다음 통나무가 겹치지 않는다면 탐색을 종료한다.

 

그 다음 통나무부터는 다른 그룹으로 합치면 된다.

---

오랜만에 풀어서 그런지 구현할 때 약간 버벅였다;;