unilep   4년 전

정답은 맞았습니다.

하지만 밑의 방식으로 접근해봤는데 시간초과가 나서

입력제한을 보니 당연히 시간초과가 나는 방식이더라구요.


밑의 방식은

나무 1개 의 weight, x좌표, y좌표 를 vector<tree> 에 넣고 weight를 기준으로 오름차순 정렬합니다.

그리고 vector를 순차탐색하면서 LIS를 구하는 방법으로 해봤습니다.

아래의 방법을 개선하여 시간초과 안나게 할 수는 없을까요?

sgchoi5   4년 전

우선, LIS 를 구하는 알고리즘을 O(N2) 이 아닌 O(NlogN) 방식으로 해야 될 듯 합니다.

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