[Algorithm] BOJ 11568 민균이의 계략

문제 링크

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

문제 풀이

이 문제는 n의 범위가 1000이라서 2중 반복문을 이용해서 $O(n^2)$의 시간복잡도로도 풀이가 가능하다.

• cache[i] : i번째 인덱스에서 끝나는 LIS의 최대 길이
• j를 0부터 i까지 증가시키면서, cache[i]에 저장되어있는 값과 numbers[j]를 LIS에 포함시켰을 때 LIS의 길이를 비교하면서 cache[i]를 업데이트한다.

하지만 이분탐색을 이용하면 시간복잡도를 $O(nlogn)$ 으로 개선할 수 있다.

• 길이 저장이 아닌, LIS 자체를 이분탐색을 이용해 구성해나가는 풀이이다.
• LIS를 구성하기 위해, numbers를 하나씩 돌면서 그 숫자가 LIS 배열에 들어갈 위치를 이분 탐색을 이용해서 구한다.

문제 코드 1

시간 복잡도 : $O(n^2)$

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

const int MAX = 1001;

int main() {

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int numbers[MAX], cache[MAX];
    for (int i=0; i<n; i++) {
        cin >> numbers[i];
        cache[i] = 1;   // 모든 수에 대해, 해당 수를 수열에 포함시켰을 때 수열의 최소 길이는 1임
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<i; j++) {
            // i 번째 숫자를 기준으로 0번째 수부터 검사하면서, cache[i]에 저장되어있는 값보다 j를 포함시켰을때의 길이가 더 길면 업데이트
            if (numbers[j] < numbers[i] && cache[i] < cache[j] + 1) {
                cache[i] = cache[j] + 1;
            }
        }
    }
    cout << *max_element(cache, cache + n);

    return 0;
}

문제 코드 2

시간 복잡도 : $O(nlogn)$

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

const int MAX = 1001;

int binarySearch(int* lis, int l, int r, int targetNum) {
    int mid;
    while (l < r) {
        mid = l + r / 2;
        if (lis[mid] < targetNum) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return r;
}

int main() {

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int numbers[MAX], lis[MAX];
    for (int i=0; i<n; i++) {
        cin >> numbers[i];
    }
    
    int end = 0;
    lis[0] = numbers[0];
    for (int i=1; i<n; i++) {
        // 현재 숫자가 lis의 마지막 인덱스에 있는 숫자보다 크면, list 맨 뒤에 현재 숫자를 넣고 lis의 마지막 인덱스를 가리키는 변수의 값을 증가시킨다
        if (lis[end] < numbers[i]) {
            lis[end++ + 1] = numbers[i];
        } else { // 현재 숫자가 lis의 마지막 인덱스에 있는 숫자보다 작으면 이분탐색으로 들어갈 자리를 찾아준다
            int index = binarySearch(lis, 0, end, numbers[i]);
            lis[index] = numbers[i];
        }
    }
    cout << end + 1;

    return 0;
}