백준 14003. 가장 긴 증가하는 부분 수열 5

티스토리 뷰

tose33 2023. 8. 14. 15:13

14003번: 가장 긴 증가하는 부분 수열 5

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

우선 O(N*N) 시간복잡도를 갖는 LIS 탐색이 아닌 O(N*logN) 을 갖는 탐색을 해야한다.

백준 2352. 반도체 설계 (N*logN LIS)

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호,

tose33.tistory.com

문제는 이 방법은 LIS 의 크기만 구할수 있고 실제 수열 자체는 구할수 없다.

이 문제는 수열 자체도 구해야 한다.

방법은 idx[] 배열을 만들어 idx[i] = j // a[i] 는 LIS 의 j 번째에 있음을 기록하는 것이다.

[ 백준 14003 ] 가장 긴 증가하는 부분수열5 (C++)

백준의 가장 긴 증가하는 부분수열5(14003) 문제이다. [ 문제 바로가기 ] [ 문제풀이 ] 이 문제를 풀기전에, 그리고 이 글을 읽어보시기 전에 다음 링크에 걸려있는 문제를 먼저 풀어보고 오시는 것

yabmoons.tistory.com

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함