[백준]2568번 전깃줄-2 문제 풀이

문제 풀이 고려해야할 점더보기입력 데이터의 수는 100000개 이하로 최악의 경우를 생각하면 O(nlogn)의 시간 복잡도로 문제를 해결해야 한다. 길이만 출력하는 것이 아닌 제거해야 하는 전깃줄의 번호도 출력해야 하기 때문에 각 경우에 제거되는 혹은 남는 전깃줄의 번호를 저장하고 추적해야 한다. 출력하는 것은 A 기둥의 번호이다. 실수로 B기둥의 번호나 임의로 부여한 인덱스를 출력하지 않도록 주의해야 한다.  문제  해결 아이디어더보기겹치지 않는 경우를 찾으려면 왼쪽과 오른쪽 인덱스가 서로 교차하지 않도록 전깃줄을 선택하면 된다. 즉 왼쪽과 오른쪽 모두 증가하는 전깃줄의 경우의 수 중 가장 많은 수의 전깃줄이 배치된 것을 찾으면 된자. (LIS 문제)가장 긴 증가하는 부분수열은 DP와 이분 탐색으로 풀..
알고리즘/코딩테스트 2024. 10. 29. 16:46
1