[백준] 12015번: 가장 긴 증가하는 부분 수열 2 - C

• 12015번: 가장 긴 증가하는 부분 수열 2
  https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

---

비슷한 문제 - https://www.acmicpc.net/problem/11053 '11053번: 가장 긴 증가하는 부분 수열' 
11053번 문제는 for문 2번 돌려서 풀었다. 

 

12015번 문제는 N 범위만 다르길래 배열 범위만 1,000,001로 바꿔서 제출했더니 

시간 초과가 뜬다..

for문을 2번 쓰면 시간 복잡도가 O(n^2)라서 최악의 경우엔 1,000,000 * 1,000,000 이라고 한다..

따라서 nlog(n) 으로 줄이기 위해 이분 탐색을 사용해야 한다.

 

풀이

ex)

주어진 수열 A를 {10, 20, 40, 30, 15, 70, 50} 차례대로 입력 받는다고 합시다

 

1. (10 입력) 처음엔 arr[0]에 10 넣기

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	...
10

현재 최대 길이 : 1

{10, 20, 40, 30, 15, 70, 50}

 

 

2. (20 입력) arr의 끝 값(10)보다 크므로 뒤에 20 넣기

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	...
10	20

현재 최대 길이 : 2

{10, 20, 40, 30, 15, 70, 50}

 

3. (40 입력) arr의 끝 값(20)보다 크므로 뒤에 40 넣기

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	...
10	20	40

현재 최대 길이 : 3

{10, 20, 40, 30, 15, 70, 50}

 

4. (30 입력) arr의 끝 값(40)보다 작거나 같으므로 arr에서 30보다 작은 값 중 가장 큰 값(20) 뒤에 넣기

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	...
10	20	40 30

30보다 작은 값 중 가장 큰 값을 찾을 때 이분 탐색을 사용한다

 

현재 최대 길이 : 3

{10, 20, 40, 30, 15, 70, 50}

 

5. (15 입력) arr의 끝 값(30)보다 작거나 같으므로 arr에서 15보다 작은 값 중 가장 큰 값(10) 뒤에 넣기

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	...
10	20 15	30

엥?? 이렇게 섞여도 되나???

처음엔 이해하기 힘들었다.. ㅜ 

하지만

{10, 20, 40, 30, 15, 70, 50}

{10, 20, 40, 30, 15, 70, 50}

이렇게 두가지 경우가 동시에 존재한다고 보면 이해하기 쉬울 것이다. 아마도..?

 

현재 최대 길이 : 3

{10, 20, 40, 30, 15, 70, 50}

{10, 20, 40, 30, 15, 70, 50}

 

6. (70 입력) arr의 끝 값(30)보다 크므로 뒤에 70 넣기

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	...
10	15	30	70

현재 최대 길이 : 4

{10, 20, 40, 30, 15, 70, 50}

{10, 20, 40, 30, 15, 70, 50}

 

7. (50 입력) arr의 끝 값(70)보다 작거나 같으므로 arr에서 50보다 작은 값 중 가장 큰 값(30) 뒤에 넣기

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	...
10	15	30	70 50

현재 최대 길이 : 4

{10, 20, 40, 30, 15, 70, 50}

{10, 20, 40, 30, 15, 70, 50}

 

입력이 끝나면 arr의 최대 길이인 4가 정답이 된다.

 

arr이 10, 15, 30, 50 이지만 실제 '가장 긴 증가하는 수열'은 10, 20, 30, 50(또는 10, 20, 30, 70 또는 10, 20, 40, 50 등등..?) 이다.

따라서 이 방법은 '가장 긴 증가하는 수열'의 길이만 구할 수 있고 수열 자체는 다를 수 있다.

 

코드

#include<stdio.h>
#include<string.h>
int arr[1000001];

int lower(int len, int a) {
    int st = 0;
    int en = len;
    int md = en;
    while(st < en) {
        md = (st+en)/2;
        if(arr[md] < a) st = md + 1;
        else en = md;
    }
    return en;
}

int main() {
    int n, arr_len = 0, a, low;
    memset(arr, 0, sizeof(arr));
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%d", &a);
        if(i==0) arr[0] = a;
        if(arr[arr_len - 1] < a) {
            arr[arr_len] = a;
            arr_len++;
        } else {
            low = lower(arr_len, a);
            arr[low] = a;
        }
    }
    printf("%d", arr_len);
}

틀린 부분 있으면 댓글 달아주세요!