2352번 반도체 설계

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

LIS 문제이다.

n이 40,000이나 되기 때문에, O(n^2)으로는 풀지 못 한다.

따라서, lower_bound()를 활용하여 O(nlogn)으로 풀어야 한다.

참고 : https://hsdevelopment.tistory.com/464

시간 초과 코드(O(n^2))

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 40001
 
int n, ans, dp[Max];
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
    int input;
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
        v.push_back(input);
    }
 
    for (int i = 0; i < v.size(); i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (v[i] > v[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        ans = max(ans, dp[i]);
    }
 
    printf("%d\n", ans);
 
    return 0;
}

정답 코드(O(nlogn))

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 40001
 
int n;
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
    int input;
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
 
        int idx = lower_bound(v.begin(), v.end(), input) - v.begin();
 
        // 찾을 자리가 없다면(찾을 자리가 없다는 것은 idx의 값이 v.size()와 같다.)
        if (idx == v.size()) {
            v.push_back(input);
        }
        else {
            // 위치를 찾았다면 그 곳에 원래 있던 값 대신에 input을 넣어준다.
            v[idx] = input;
        }
    }
 
    printf("%d\n", v.size());
 
    return 0;
}