[C++]백준 - 14003번 문제

14003번: 가장 긴 증가하는 부분 수열 5 (acmicpc.net)

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

 

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

---

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

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

 

입력

---

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

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

 

 

출력

---

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

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

 

 

---

 

생각해 볼 점

---

입력값의 크기와 메모리 제한을 보아, 12015번 문제와 같이 풀어야 함을 알 수 있습니다.

 

즉, Lower_Bound를 이용한 문제인데, 이번에는 수열도 함께 출력해야 하므로, trace라는 벡터를 하나 사용하여

 

새 입력이 들어올 때마다 기록하도록 합니다.

 

Trace 배열에는 Pair타입으로 입력된 index와 실제 값을 함께 저장하겠습니다.

 

만약 입력이 다음과 같으면,

입력 : {10, 20, 10, 30, 15, 50}

 

Lower Bound 배열 : {10, 15, 30, 50}

Trace 배열 : {<0, 10>, <1, 20>, <0, 10>, <2, 30>, <1, 15>, <3, 50>}

실제 답 : {10, 20, 30, 50}

 

위와 같이 저장됩니다.

 

Trace 배열을 역순으로 탐색하여 index 역순으로 꺼내면 다음과 같습니다.

 

Trace 배열 : {<0, 10>, <1, 20>, <0, 10>, <2, 30>, <1, 15>, <3, 50>}

        <--------------------------------------진행 방향---------------

 

index == 3일때 : 50

index == 2일때 : 30

index == 1일때 : 20

index == 0일때 : 10

 

즉, 정답 수열 10, 20, 30, 50을 꺼낼 수 있습니다.

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int main() 
{
    int N;
    scanf("%d", &N);

    vector<int> LIS;
    vector<pair<int, int>> trace;
    int LIS_size = 0;
    
    //Lower Bound를 이용
    for(int i = 0; i < N; i++)
    {
        int input;
        scanf("%d", &input);
        vector<int>::iterator it = lower_bound(LIS.begin(), LIS.end(), input);
        
        int index = it - LIS.begin();
        
        //input을 새로 추가할 경우
        if(LIS_size == index)
        {
            LIS.push_back(input);
            trace.push_back({index, input});
            LIS_size++;
        }
        //기존의 input을 교체하는 경우
        else 
        {
            LIS[index] = input;
            trace.push_back({index, input});
        }
    }
    stack<int> st;
    
    int index = LIS_size - 1;
    //Trace배열에 담았던 input을 역추적 
    for(int i = N - 1; 0 <= i; i--)
    {
        if(trace[i].first == index)
        {
            st.push(trace[i].second);
            index--;
        }
    }
   
    
    printf("%d\n", LIS_size);
    while(!st.empty()) 
    {
        printf("%d ", st.top());
        st.pop();   
    }
	return 0;
}

 

그 외

---

[Python] 백준 14003번: 가장 긴 증가하는 부분 수열 5 :: Robert Chopin's CODE (tistory.com)

[Python] 백준 14003번: 가장 긴 증가하는 부분 수열 5

 

큰 도움이 된 반례를 제공해 준 링크입니다.