LIS, Bitonic

LIS

LIS에 대한 설명은 문제를 읽어보면 이해가 빠를것이다.

6개의 수를 가진 수열
10 20 10 30 20 50이 있다고 하자.

이때 최장 증가 부분수열을 어떻게 구해야할까?

풀이

일단 모든 자리는 기본적으로 1이라는 최장수열을 가진다. 자기자신이 그 수열이 되기 때문이다.

2번째 수의 경우, 10 20이기에 2가 최장수열이 된다.

3번째 수의 경우, 10 20 10이기에 자기자신이 최장수열이 된다.

4번째 수의 경우, 10 20 10 30 이기에 10 20 x 30 해서 3짜리 길이의 수열을 가진다.

여기서 한가지 규칙을 발견할 수 있다.

현재 자기 자리수 이전의 나보다 현재 값보다 작은 숫자들의 최장수열중 max값 + 1이 내가 가지는 최장수열의 값.

이라는 규칙을 찾을 수 있다.

이를 식으로 나타내려면 이중 for문을 사용해야한다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int n;

int dp[1001];

int main() {
    cin >> n;
    int arr[n+1];
    fill_n(dp, 1001, 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    for (int i = 2; i <=n; i++) {
        for (int j = 1; j <= i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i] > max) max = dp[i];
    }
    cout << max;
}

이렇게 구하면 LIS는 쉽게 구해진다.

Bitonic

이름은 거창하지만 LIS를 한번 뒤집고, 1을 빼주면 된다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int n;

int dp1[1001];
int dp2[1001];
int ans[1001];


int main() {
    cin >> n;
    int arr[n+1];
    fill_n(dp1, 1001, 1);
    fill_n(dp2, 1001, 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp1[0] = 0;
    dp2[0] = 0;

    for (int i = 1; i <=n; i++) {
        for (int j = 1; j <= i; j++) {
            if (arr[i] > arr[j]) {
                dp1[i] = max(dp1[i], dp1[j] + 1);
            }
        }
    }
    
    for (int i = n; i >= 1; i--) {
        for (int j = n; j >= i; j--) {
            if (arr[i] > arr[j]) {
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
    }
    int max = 0;
    int counter = 1;
    for (int i = 1; i <= n; i++) {
        ans[counter] += dp1[i];
        counter++;
    }
    counter = n;
    for (int i = n; i >= 1; i--) {
        ans[counter] += dp2[i];
        counter--;
    }
    for (int i = 1; i <= n; i++) {
        //cout << ans[i] << " ";
        if (ans[i] > max) max = ans[i];
    }
    //cout << "\n";
    cout << max - 1;
    
}

우선 한번은 정상적으로 LIS를 구한다.
그리고 다시 한번 뒤에서부터 역순으로 순환하면서 그 값들을 구한다.

역순은 n부터 시작하며, 1까지 가야한다.

그 후 이 두 dp값들을 하나의 배열에 각 수의 순서에 맞게 모두 더해준다.

다만 이때, 역순 진행은 역순으로 더해야한다.

이렇게 더한 값은 사실 원소가 하나씩 중복되고 있다.

예를들어 1234521의 경우
12345가 더해지고
5 2 1이 더해진다.
5가 한번 중복되는 것이다.

따라서 1을 빼주고, 해당 배열 중 가장 큰 값이 정답이 된다.

정리

아직 전깃줄 LIS문제가 하나 더 남았다