[3745] 오름세

https://www.acmicpc.net/problem/3745

3745번: 오름세

최장증가 부분수열(LIS) 문제다. DP로 푸는 방법, 이분탐색을 이용하는 방법, 세그먼트 트리를 이용한 방법 총 세 가지 방법이 있다. 

지난번에는 이분탐색을 통해 문제를 풀어보았고 현재 세그먼트 트리를 공부 중이라, 이번에는 세그먼트 트리를 이용하여 접근해 보았다. 이분탐색 풀이와 마찬가지로 O(N*logN)의 복잡도로 풀 수 있다.

 

풀이

해당범위의 LIS의 길이를 담은 구간 최댓값 세그먼트 트리를 생성한다. 초기값은 0이다.

 

주가를 입력받을 때, (가격, 인덱스) 튜플형태로 입력받은 뒤, 주가를 기준으로 오름차순, 주가가 같다면 인덱스 기준 내림차순으로 정렬을 한다. 이후 정렬된 주가정보를 순차 탐색하면서 세그먼트 트리를 갱신해 주면 된다.

 

원리는 다음과 같다. 주가가 작은 값부터 탐색을 시작하기에 들어오는 정보 (주가, 인덱스)는 곧 0부터 인덱스 i까지의 최장증가 부분수열의 길이이며, 해당 수열에 입력된 주가 값을 덧붙이면(+1) 새로운 최장증가부분수열의 길이를 구할 수 있는 것이다.

 

예제 [5,2,1,4,5,3]을 기준으로 세그먼트를 완성시켜 보자.

가장 먼저 0으로 초기화된 세그먼트트리와 (값, 인덱스) 튜플형태를 정렬한 모습이다.

 

가장 먼저 인덱스 0-2 값을 조회, 길이가 0이고 여기에 배열의 가장 최솟값인 1을 붙여 길이가 1인 LIS길이가 생성된다. 해당 범위인 0-2까지의 LIS길이가 1이 되는 것이다. 따라서 0-2 범위를 1로 갱신하게 된다.

 

다음 값은 2이며 범위 0-1에 해당하는 값을 참고, 해당 수열에 2를 붙여 갱신하게 된다. 다음과 같은 작업을 반복하면 된다.

0-5 범위의 최장수열에 3을 붙여 길이 2인 최장수열이 생성된다. 해당 범위의 트리에 값 갱신.

 

0-3 범위 조회 후 갱신

 

0-4 범위 조회 후 갱신

 

가장 마지막으로 0-0 범위 조회 후 갱신

 

다음과 같은 과정으로 트리가 완성되며 문제에서 요구하는 전체 범위의 최장증가 부분수열의 길이는 루트 노드에 담겨있게 된다.

 

정답 코드

스위프트의 경우 입력 부분에서 제약이 생긴다. 라인이 분리되어서 주가가 입력되는 경우가 들어오게 되는데, 기본적인 입력으로는 해결하기 까다로워 보였다. 결국 해당 문제 질문 게시판에서 발견한 honghoker님의 글을 참고해서 입력을 처리하였다.