2673번 - 교차하지 않는 원의 현들의 최대집합
제 접근은 다음과 같습니다.
1번 점을 기준으로 원을 찢어 수평선으로 만듭니다. 이때, 기존 선들은 유연하게 곡선으로 늘릴수있다고 가정합니다.선이 겹치지 않기 위해선, 다른 선의 내부에 있거나 외부에 있어야합니다. 최대로 겹쳐지지 않는 선의 개수수는 LIS를 이용해 구합니다.2~100번 점을 기준으로도 같은 방식으로 처리해줍니다. 이중 가장 큰 값을 정답으로 출력합니다.
1. 각 선 정보{a,b}를 항상 a<b를 유지하며, 오름차순정렬 합니다.2. a기준으로 오름차순이므로, 다른 점b가 작아질경우 현이 선이 겹치지 않습니다.3. 내림차순 LIS를 적용합니다.
예제는 맞았으나, 질문게시판에 있는 케이스들에 대해 답이 오히려 적게 나오고 있습니다.왜 이 접근이 틀린것인지 궁금합니다
댓글을 작성하려면 로그인해야 합니다.
ryu_eclipse 1년 전
제 접근은 다음과 같습니다.
1번 점을 기준으로 원을 찢어 수평선으로 만듭니다. 이때, 기존 선들은 유연하게 곡선으로 늘릴수있다고 가정합니다.
선이 겹치지 않기 위해선, 다른 선의 내부에 있거나 외부에 있어야합니다. 최대로 겹쳐지지 않는 선의 개수수는 LIS를 이용해 구합니다.
2~100번 점을 기준으로도 같은 방식으로 처리해줍니다. 이중 가장 큰 값을 정답으로 출력합니다.
1. 각 선 정보{a,b}를 항상 a<b를 유지하며, 오름차순정렬 합니다.
2. a기준으로 오름차순이므로, 다른 점b가 작아질경우 현이 선이 겹치지 않습니다.
3. 내림차순 LIS를 적용합니다.
예제는 맞았으나, 질문게시판에 있는 케이스들에 대해 답이 오히려 적게 나오고 있습니다.
왜 이 접근이 틀린것인지 궁금합니다