코드의 내용은 다음과 같습니다.

1. 입력 받은 좌표를 넣을 때, 다음과 같은 의사 결정을 합니다. 

(a) answer_list라는 좌표 모음집에 있는 모든 좌표와 a,b라는 곳에 저장된 좌표가 만나지 않으면 a,b는 answer_list에 넣습니다.

     좌표가 만나지 않는 것을 비교하는 방법은 다음과 같습니다.

     (한 좌표가 a,b  다른 좌표가 c,d라고 했을 때, min(a,b) < max(a,b) < min(c,d) < max(c,d) 거나 min(a,b) < max(a,b) < min(c,d) < max(c,d) 이면 각 좌표가 그리는 선분이 만나지 않기 때문에, 이들은 연결되지 않습니다)

(b) answer_list라는 좌표 모음집에 있는 좌표 중 하나라도 만나는 것이 있다면, 그 인덱스를 뒤로 넘겨주어 값을 수정합니다.  

    수정하는 방법은 다음과 같습니다. 

     두 좌표의 4개의 점 중 가장 최소값과 최대값을 뽑아 각각 채워넣습니다.

   예를 들어 (1,5) , (3,-1)이 있었다면, 4개 점 중 가장 작은 -1, 그리고 가장 큰 5만 answer_list에 남게 됩니다.

위와 같은 로직으로 연결되는 것들을 짜보았는데... 자꾸 틀렸다고 나오네요..

여러 반례들을 쳐봤으나... 안되네요 ㅠ.ㅠ... 도움 주시면 너무 감사하겠습니다. 

 

        

circlezer0   3년 전

우선, 입력 조건에 x<y가 있으므로 min(a,b), max(a,b)는 할 필요가 없습니다.

그리고 위 코드의 시간복잡도도 O(n^2)으로 문제를 풀 수 없습니다.

input

3
1 3
8 10
2 9

output : 10

answer : 9

댓글을 작성하려면 로그인해야 합니다.