[Softeer/소프티어][level4] 징검다리2 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=393&sw_prbl_sbms_sn=18407

 

 

[난이도] level4
[유형] DP

[풀이]
이전 포스팅의 징검다리 문제보다 어려운 문제입니다.
이유는 아래와 같습니다.
1. N 제한이 10만을 넘어가므로 LIS를 구할 때 lower_bound를 이용하는 O(NlogN) 방법을 이용해야 합니다.
2. 단순 LIS를 구하는 것이 아닌 증가했다가(LIS) 감소하는(LDS) 변곡점이 있는 LIS + LDS sequence를 구해야 합니다.

0~N-1 번 돌을 변곡점으로 확정짓고 그 점부터 좌우로 퍼져나가는 LIS 혹은 LDS를 구하려고 하면 O(N^2logN)이 되어 시간초과에 빠지게 됩니다.

그러므로 앞에서부터 LIS를 한번 구해서 정보들을 저장 한 뒤, 뒤에서부터 LIS를 구해주면서
앞에서부터 LIS를 구해주면서 저장한 정보를 이용해 답을 구하는 O(NlogN) 해법을 이용해야 합니다.

아래 코드에서는 asc[300000], ascmax[300000] 배열을 선언하여 사용하였습니다.
asc[i] : 0~i 돌을 사용한 LIS의 크기.
ascmax[i] : 0~i 돌을 사용한 LIS의 마지막 값.

앞에서부터 LIS를 구하면서 위의 정보를 저장 한 뒤,

뒤에서부터 LIS를 돌려줍니다.
만약 i번 돌이 변곡점이 된다면 포함될 수 있는 최대 돌의 개수는
int v = dp.size() (N-1~i 돌을 사용한 LIS의 크기) + asc[i] (0~i 돌을 사용한 LIS의 크기)
이 됩니다.

하지만 여기서 예외처리 해주어야 할 것이 i번 돌이 좌측 LIS, 우측 LIS에 모두 포함될 경우입니다.
이 경우에는 변곡점 i번 돌을 1개 빼주어야 하므로
ascmax[i]를 확인해서 a[i]와 같은지, dp.back() (현재 LIS의 가장 큰 값) 이 a[i]와 같은지를 모두 체크해서
둘다 같다면 v-- 연산을 해주면 됩니다.

이는 모든 돌의 높이가 다르다는 것이 문제의 조건에 나와있기 때문에 가능합니다.

 

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int ans,N,a[300001],asc[300001],ascmax[300001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);

    vector<int> dp = {a[0]};

    for(int i=1;i<N;i++){
        int idx = lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        if(idx == dp.size()) dp.push_back(a[i]);
        else dp[idx]=a[i];
        asc[i]=dp.size();
        ascmax[i]=dp.back();
    }

    dp.clear();
    dp.push_back(a[N-1]);

    for(int i=N-2;i>=0;i--){
        int idx = lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        if(idx == dp.size()) dp.push_back(a[i]);
        else dp[idx]=a[i];
        int v = dp.size()+asc[i];
        if(ascmax[i]==a[i] && dp.back()==a[i]) v--;
        ans=max(ans,v);        
    }
    printf("%d",ans==0?1:ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/징검다리2.cpp