[BAE/<JOON> 문제풀이] 2352. 반도체 설계

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

2352번: 반도체 설계

평범한 증가수열 문제인줄 알았는데 일반적인 N^2 해법으로는 안풀리고 더 최적화된 방법을 사용해야한다.

 

일반적인 증가수열의 해법을 복기해보자.

 

각 수열의 인덱스마다 그 지점까지의 최장 증가수열 길이를 저장해놓고

 

현재 지점과 이전 지점을 비교하여 증가 수열이라면 값을 갱신하는 식으로 최장증가수열의 길이를 구했다.

 

즉, 각각의 지점들에 대해 이전 지점들을 모두 비교하므로 시간 복잡도는 N^2이다.

 

N의 최댓값이 40000이므로 N^2는 1600000000 이다. 시간 제한이 2초여도 제한 시간안에 답이 나오긴 힘들다.

 

아래는 N log N의 최장증가수열을 구하는 알고리즘이다.

 

dpc[i] : 길이가 i인 최장증가수열 중, 마지막 값이 가장 작은 수열의 마지막 값.
dpc배열은 최댓값으로 초기화
ml : 현재까지 발견된 가장 긴 수열의 길이

dpc[1] = arr[1];
int ml = 1; 
for (int i = 2; i <= n; i++) { 
//이미 발견된 최장수열을 연장할 경우, 
        if (arr[i] > dpc[ml]) {
            ml++;
            dpc[ml] = arr[i];
        }
//이미 발견된 길이의 수열일 경우, 마지막 값을 최솟값으로 갱신함
        else {
            auto p = lower_bound(dpc.begin(), dpc.end(), arr[i]);        
            *p = min(*p, arr[i]);
        }               
    }

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    vector<int> arr, dp, dpc;
    cin >> n;
    dp.resize(n + 1);
    dpc.resize(n + 1);
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp[i] = 1;
        dpc[i] = 2147483647;
    }    
    dpc[0] = (-2147483647 - 1);
    dpc[1] = arr[1];
    int ml = 1;
    for (int i = 2; i <= n; i++) {   
        if (arr[i] > dpc[ml]) {
            ml++;
            dpc[ml] = arr[i];
        }
        else {
            auto p = lower_bound(dpc.begin(), dpc.end(), arr[i]);        
            *p = min(*p, arr[i]);
        }               
    }

    for (int i = n; i >= 1; i--) {
        if (dpc[i] != 2147483647) {
            cout << i; 
            return 0;
        }
    }

    cout << dp[n];
    return 0;
}