백준 14002번 가장 긴 증가하는 부분 수열 4 문제풀이 c++

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

14002번: 가장 긴 증가하는 부분 수열 4

문제 해석

백준 11053번문제에서는 길이만 구하는 것이 끝이였으나 이번 문제에선 길이와 수열을 둘다 구하는 문제이다.

https://anwltjdzheldsbql.tistory.com/7 에 자세한 설명은 다 되어있다.

저번 글에서 마지막에 정렬을하고난후 길이를 출력한것에 수열 출력 부분만 더 추가해주면 된다.

어떻게 할까 고민을 했는데 아래와 같이 생각을하였다

예제처럼

6 

10 20 10 30 20 50

가 입력으로 들어오면 가장 큰 길이는 4이고 그것은 50으로 끝난다.

그렇다면 그 다음에 찾아야 하는것은 무엇? -> 50보다 작은 수로 끝나면서 길이가 3인것 : 30으로끝나고 길이가 3

그렇다면 그 다음에 찾아야 하는것은 무엇? -> 30보다 작은 수로 끝나면서 길이가 2인것 : 20으로끝나고 길이가 2

그렇다면 그 다음에 찾아야 하는것은 무엇? -> 20보다 작은 수로 끝나면서 길이가 1인것 : 10으로끝나고 길이가 1

그렇다면 답은 10 20 30 50이다.

즉 길이가 긴 것을 시작점으로 길이가 1이 될때까지를 찾는것이다.

그렇기 때문에 정렬이 필요하였고 뒤에서 부터 반복문을 쓰면 된다.

출력은 작은것부터 해야하므로 스택에 넣었다가 마지막에 출력하는방법을 사용하였다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
stack <int> st;
vector < pair<int,int> > v; //길이,끝수
void solve();
int a[1001];
int n;
int ans=0;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    solve();
}
void solve(){
    v.push_back({0,0});
    for(int i=1; i<=n; i++)
    {
        int mx=0;
        for(int j=0; j<i; j++)
        {
            if(a[j]<a[i])
            {
                mx=max(mx,1+v[j].first);
            }
        }
        v.push_back({mx,a[i]});
    }
    sort(v.begin(),v.end());
    int length=v[v.size()-1].first;
    int end_num=v[v.size()-1].second;
    cout<<length<<"\n";
    st.push(end_num);
    for(int i=v.size()-2; i>=1; i--)
    {
        if(v[i].first!=length&&v[i].second<end_num)
        {
            length=v[i].first;
            end_num=v[i].second;
            st.push(end_num);
        }
    }
    while(!st.empty())
    {
        cout<<st.top()<<" ";
        st.pop();
    }
}

 

코드에는 길이가 1일때까지 찾지않고 그냥 끝부터 처음까지 찾는데 사실 길이가 1인것을 찾으면 바로 종료 시키는게 더 나을것 같다는 생각을 글을 쓰면서 알게 되었다.