[백준] 2352: 반도체 설계

0. 문제 주소

 

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

2352번: 반도체 설계

 

 

1. 풀이

 

 

교점이 생기면 안 된단다. 그냥 LIS 문제다.

 

LIS 풀이는 여러가지가 있지만, 이 문제에선 N 제한이 40000이므로 dp, 즉 O(N^2)로는 풀 수 없다.

 

lower_bound를 사용하면 O(n log n)으로 쉽게 풀 수 있다.

 

 

먼저 빈 배열 d를 설정해두고, 기존 배열 nums를 순회하며 다음과 같은 규칙으로 d를 채워 나간다.

 

 

---

0. 먼저 기존 배열 nums에서 순회하는 중인 수를 curr라고 하자.

 

1. lower_bound를 이용하여, 만약 d의 가장 앞부터 보아 curr 이상인 수가 등장한다면,

처음 등장하는 위치에 curr를 대체시킨다.

 

2. 등장하지 않는다면, d 맨 뒤에 curr를 추가한다.

---

 

문제에 나온 예시로 설명하겠다 : 4 2 6 3 1 5

 

 

nums : 4 2 6 3 1 5

d : 4

 

처음이니까 4 추가.

 

 

nums : 4 2 6 3 1 5

d : 2

 

curr = 2일 때, 2 <= 4 이므로 4를 2로 대체한다.

 

 

nums : 4 2 6 3 1 5

d : 2 6

 

curr = 6일 때, 6 이상인 수가 d에 없으므로 d 맨 뒤에 6을 추가한다.

 

 

nums : 4 2 6 3 1 5

d : 2 3

 

curr = 3일 때, 3 <= 6 이므로 6를 3으로 대체한다.

 

nums : 4 2 6 3 1 5

d : 1 3

 

curr = 1일 때, 1 <= 2 이므로 2를 1로 대체한다.

 

nums : 4 2 6 3 1 5

d : 1 3 5

curr = 5일 때, 5 이상인 수가 d에 없으므로 d 맨 뒤에 5을 추가한다.

 

 

위와 같이 nums를 모두 순회했을 때, d 배열의 길이가 LIS의 길이가 된다.

 

그리디적인 해법이라고 볼 수 있다. 앞으로 이어질 nums의 원소들에 대해서,

LIS가 더 유리하게 만들어질 수 있도록 d 배열을 갱신해나가는 것이다.

 

다만 d 배열의 원소는 실제 LIS를 이루는 값들과는 관계가 없다. 

 

실제 LIS를 역추적하려면, d의 값이 curr로 대체될 때 바로 앞에 있는 수를 새로운 배열에 저장해주는 방법이 있는데,

 

이건 나중에 관련 문제가 나올 때 포스팅 해야겠다.

 

 

2. 풀이 코드

 

* 유의할 점

 

#include <bits/stdc++.h>
#define MAX 40005
#define INF 987654321

using namespace std;

int N;
int nums[MAX];
int d[MAX];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &N);

    for (int i=1;i<=N;i++){
        scanf("%d", &nums[i]);
    }

    d[1] = nums[1];
    int len = 1;

    for (int i=2;i<=N;i++){
        int curr = nums[i];
        if (d[len] < curr) {
            d[++len] = nums[i];
            continue;
        }
        int ind = lower_bound(d+1, d+len+1, curr) - d;
        d[ind] = nums[i];
    }
    printf("%d\n", len);
}