[백준] 14003번 가장 긴 증가하는 부분 수열5 문제 풀이(c++)

문제 링크 - https://www.acmicpc.net/problem/14003

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

 

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

 

아이디어

우선, 가장 긴 증가하는 부분 수열의 "길이"를 구하는 방법은 제가 이전 포스팅에서 설명드렸던 방식과 같습니다.

(12015번 가장 긴 증가하는 부분 수열 2 풀이 https://nomadsjh.tistory.com/66) 

lower bound를 이용하는 것인데요.

하지만, 이 방법으로만 코드를 짜면 LIS의 값을 직접 구할 수는 없기 때문에 다른 방법을 추가해야 합니다.

 

lower bound를 사용한 알고리즘으로부터 LIS를 구할 수 없었던 이유는 전체 수열 중에서 LIS에 해당하는 부분까지 탐색을 끝내도 알고리즘이 종료되지 않고 끝까지 lower bound로 업데이트를 하기 때문이었습니다. 사실 잘 와닿지 않을 수 있어서 예시를 들어 보겠습니다.

ex) (10, 30, 40, 20)이라는 수열이 있다고 합시다. 이때의 LIS는 (10, 30, 40)이죠. 그러나 lower bound 형식을 사용하면 10, 30, 40을 벡터에 push_back한 후에 lower bound(20)을 하여 최종적으로 (10, 20, 40)의 배열이 만들어집니다. 그러니까 10, 30, 40이라는 LIS가 이미 나왔지만 컴퓨터는 그걸 모르니까 이런 문제가 발생한다고 설명할 수도 있겠네요.

 

그렇다면 이 문제를 어떻게 해결할 수 있을까요?

저는 수열의 요소들에게 lower bound를 적용했을 때의 값을 저장하는 check 배열을 만들어 이를 해결했습니다.

일단 lower bound를 활용하여 LIS의 길이는 구할 수 있기 때문에 LIS의 길이는 알고 있다고 생각하겠습니다.

LIS의 길이를 안다는 뜻은 LIS의 마지막 수, 즉 LIS에서 가장 큰 수에 대한 정보를 안다는 뜻과 동일합니다.

 

아까 check 배열은 수열의 모든 요소들에게 lower bound를 적용했을 때의 값을 저장해 놓은 배열이라고 했습니다.

그러니까 LIS에서 가장 큰 수의 lower bound 값은 (LIS의 길이-1)일 것입니다.(배열의 인덱스가 0부터 시작해서)

위에서 사용한 예시를 다시 끌고 와서 표로 정리해보겠습니다.

입력된 수열	10	30	40	20
check	0	1	2=(LIS의 길이-1)	1

 

그렇다면 check배열의 인덱스가 0부터 n-1까지라고 했을 때

check[i]의 값 == (LIS의 길이-1)이라는 조건문을 만족하는 (입력된 수열)arr[i]가 LIS의 가장 큰 수이겠군요.

 

그럼 우리는 for 반복문을 통해 check 배열을 n-1부터 0까지 탐색을 진행하며

위 조건을 만족할 때마다 ans라는 벡터에 arr[i]값을 넣어주고 length-- //(LIS의 길이를 length라고 했을 때)

를 해주면 됩니다.

 

최종적으로 출력할 때는 ans벡터에 아무것도 들어있지 않을 때까지 뒤에서부터 출력해주면 되는 것이죠.

 

다시 한 번 예시를 들어 살펴보자면 다음과 같습니다. (사실 말로 하는 설명보다 예시로 하는 설명이 이해하기 더 직관적인 것 같습니다.)

 

입력된 수열 : (10, 30, 40, 20)

check 배열 : (0, 1, 2, 1)

LIS의 길이 : 3

 

(n-1부터 탐색)

check[3]=1,  (length-1)=2 ->조건 불만족

check[2]=2, (length-1)=2 -> 조건 만족 -> ans : (40, ) -> length=2;

check[1]=1, (length-1)=1 -> 조건 만족 -> ans : (40, 30, ) -> length=1;

check[0]=0, (length-1)=0 -> 조건 만족 -> ans : (40, 30, 10) -> length=0;

->length가 1보다 작으므로 break;

ans가 비워질 때까지 끝에서부터 출력 -> 10 30 40

 

소스 코드

#include<bits/stdc++.h>
using namespace std;
int check[1000001], arr[1000001];
vector<int> v,ans;
int n;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    v.push_back(arr[0]);
    int length=1;
    
    for(int i=1;i<n;i++)
    {
        int index=lower_bound(v.begin(),v.end(),arr[i])-v.begin();
        check[i]=index;
        if(v.back()<arr[i])
        {
            v.push_back(arr[i]);
            length++;
        }
        else
        {
            v[index]=arr[i];
        }
    }

    printf("%d\n",length);

    for(int i=n-1;n>=0;i--)
    {
        if(length<1) break;
        if(check[i]==length-1)
        {
            ans.push_back(arr[i]);
            length--;
        }
    }
    
    while(!ans.empty())
    {
        printf("%d ",ans.back());
        ans.pop_back();
    }
    return 0;
}