[4198번] 열차정렬

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. lis 알고리즘 :: http://www.crocus.co.kr/583

2. lds 알고리즘 :: http://www.crocus.co.kr/669

이 문제는 lis + lds - 1이 정답이 된다.

왜 lis + lds - 1이 정답일까?

9

5 6 4 7 3 8 2 9 1 를 보자.

5 기준으로 볼때 5 6 7 8 9가 올 수 있고 5 앞에는 1 2 3 4 5가 올 수 있다.

결국 1 2 3 4 5 6 7 8 9가 올 수 있으므로 lis + lds를 하고 5가 중복되니 -1을 해준 9가 답이 된다.

우선 이 문제는 DP로 해결하면 가장 쉽게 해결 할 수 있다.

그리고 DP는 O(n^2)으로 해결이 되지만, lower_bound 방식을 이용하면 O(n^2*lgn)의 시간이 걸리게 된다.

하지만 DP가 아닌 로어바운드로 어떻게 문제를 해결하는지 알기 위해 풀이를 쓰고자 한다.

lis를 구할 때는 lower_bound를 쓰되 , 현재 idx에 값을 고정시키고 현재 idx값보다 큰 값을 하나 찾아 그 값을 기준으로 lis를 조사한다.

이때 현재 idx값보다 작은 값이 나타나면 모순이 일어나므로 continue를 해주며 값을 조사해준다.

예를들어 5 6 1 2 4가 있다 보자.

현재 5를 고정 시키고 그다음 6이 나타나 5 6 이 현재 lis에 있다.

그런데 1이 와버리면 6자리에 1이 들어가게 되어 5 1이 되고 결국 5 1 2 4가 lis가 되어버린다.

실제 lis는 5 6이 되어야하는데 결국 이상한 lis가 형성되므로 현재 인덱스에 해당하는 값보다 작은 값이 나타나면 continue를 해준다.

lds도 마찬가지이다. 대신 lds를 구할 때는 lower_bound를 쓸 수 없으므로 직접 lds용 lower_bound를 형성한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n;
 
int lis(int here, vector<int> vc)
{
    vector<int> lis;
    int plis = 1;
 
    // 현재 idx값 고정
    lis.push_back(vc[here]);
 
    // 현재 idx값 보다 큰 값이 존재하면 하나 push
    int i;
    for (i = here + 1; i < n; i++)
        if (lis[0] < vc[i])
        {
            lis.push_back(vc[i]);
            plis++;
            i++;
            break;
        }
 
    // 그 다음 값부터 조사
    for (i; i < n; i++)
    {
        // 현재 idx값보다 작은 값이 나타나면 현재 기준 lis에 모순이 일어나기에 continue
        if (lis[0] > vc[i])
            continue;
 
        if (lis.back() < vc[i])
        {
            lis.push_back(vc[i]);
            plis++;
        }
        
        else
        {            
            auto it = lower_bound(lis.begin() + 1, lis.end(), vc[i]) - (lis.begin());
            lis[it] = vc[i];
        }
    }
 
    return plis;
}
 
int getLds(vector<int> lds, int start, int end, int target)
{
    int mid;
 
    while (start < end)
    {
        mid = (start + end) / 2;
 
        if (lds[mid] > target)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
int lds(int here, vector<int> vc)
{
    vector<int> lds;
    int plds = 1;
 
    // 현재 idx값 고정
    lds.push_back(vc[here]);
 
    // 현재 idx값 보다 작은 값이 존재하면 하나 push
    int i = 0;
    for (i = here + 1; i < n; i++)
        if (lds[0] > vc[i])
        {
            lds.push_back(vc[i]);
            plds++;
            i++;
            break;
        }
 
    // 그 다음 값부터 조사
    for (i; i < n; i++)
    {
        // 현재 idx값보다 큰 값이 나타나면 현재 기준 lis에 모순이 일어나기에 continue
        if (lds[0] < vc[i])
            continue;
    
        if (lds.back() > vc[i])
        {
            lds.push_back(vc[i]);
            plds++;
        }
 
        else
        {
            int pos = getLds(lds, 1, plds, vc[i]);
            lds[pos - 1] = vc[i];
        }
 
    }
 
    return plds;
}
 
int main()
{
    scanf("%d", &n);
 
    vector<int> vc(n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &vc[i]);
 
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int cntLis = lis(i, vc);
        int cntLds = lds(i, vc);
 
        ans = max(ans, cntLis + cntLds - 1);
    }
 
    printf("%d", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>