[백준 / BOJ] 14003 가장 긴 증가하는 부분 수열 5

문제

출처 : www.acmicpc.net/problem/14003

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

수열 A가 주어졌을때, 가장 긴 증가하는 부분 수열의 길이와 해당 수열을 구하는 문제다.

 

풀이

dp를 이용해 풀어야하는문제다.

수열의 크기가 1,000,000까지 가서, 이전 idx에서 가장큰 수를 N^2으로 뽑는 풀이로는 풀수없다. (매 탐색마다 자신의 뒤에서 가장 큰수를 가져오는 풀이로는 풀수없음)

 

이분탐색(혹은 세그)을 활용한 NlogN LIS알고리즘을 쓰면 풀리는 문제다.

사실 이 문제는 경로추적이 메인이기 때문에, 최장 증가 수열을 만드는 과정은 스킵하고 경로추적만 설명하겠다.

(만약, 최장 증가 수열 만드는것이 막히는 분들은 백준 12738번 을 먼저 풀어보자)

 

이분탐색을 활용한 NlogN LIS알고리즘은 항상 LIS의 최장 길이는 항상 보장하지만, 수열의 원소는 순차적으로 정렬되어있지않을수있다. 따라서, par배열을 통해 경로를 역추적 해줘야한다. 나는 이 과정을 이분탐색으로 현재 수가 어느 위치에 들어가야하는지 확인하는 부분에서 진행했다. 

우선, 아래 예제를 보고 LIS를 만들어보자

1. 

6

1 10 20 30 2 3 

위 예제에서 LIS만들어 보면,

vector<int> vec;

 

vec = 1

vec = 1, 10

vec = 1, 10, 20

vec = 1, 10, 20, 30

vec = 1, 2, 20, 30

vec = 1, 2, 3, 30

vec = 1, 2, 3, 30

다음 과 같이 만들어진다.

이때, LIS의 길이는 vec의 사이즈이므로 4인데, 1, 2, 3은 순차적으로 등장하므로 최장 증가수열이지만, 30은 2 앞에 등장하므로 vec의 원소들은 최장 증가수열이 아니다.

따라서, 벡터를 pair로 선언해서 각 원소가 등장한 idx까지 체크를 해주고, 현재 idx가 vec[idx-1]의 등장위치보다 뒤에있을경우 par배열을 업데이트 해준다. 마찬가지로 위 예제를 가지고 다시 LIS를 만드는 과정을 나타내면

 

vec<pair<int,int> > vec;

// {수열의 원소, 해당 원소의 등장idx}

 

vec = {1,1}

vec = {1,1}, {10,2}

vec = {1,1}, {10,2}, {20,3}

vec = {1,1}, {10,2}, {20,3}, {30,4}

vec = {1,1}, {2,5}, {20,3}, {30,4}

vec = {1,1}, {2,5}, {3,6}, {30,4}

par[1] = -

par[30] = 20

par[20] = 10

par[10] = 1

par[2] = 1

par[3] = 2

다음과 같다.

vec의 마지막원소 30을 기준으로 par배열을 역순으로 출력하면 1 10 20 30 이 출력될것이다.

이분탐색으로 LIS를 만드는 과정을 생각해보면 위 풀이가 항상 성립하는걸 알수있는데, 

LIS를 만드는 과정에서 더 뒤idx에 나오는 원소를 vec사이에 업데이트 해주는 이유는, 혹시 뒤에서 나올 더 긴 LIS를 대비하기 위해서이다.

즉, 위 경로를 만드는 과정에서 더 긴 LIS가 나오지않는다면, 경로 업데이트를 해주면 안되는데, 더 긴 LIS가 나온다는 뜻은, vec의 모든 원소들의 등장 idx가 바뀐다는 뜻이다. 

 

따라서 모든 원소가 바뀌기 전에는 경로가 바뀌면 안되므로, 현재 idx > vec[현재idx-1] 일때만 업데이트 해주는것이다.

 

이해가 잘 안되면

8

1 10 20 30 2 3 4 5

이걸 똑같이 해보자

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14003%20%EA%B0%80%EC%9E%A5%20%EA%B8%B4%20%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4%205/main.cpp

devxb/JJUNalgo