[BOJ] 11054. 가장 긴 바이토닉 부분 수열(DP, LIS 응용)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

LIS의 기본 동작은 여기를 참고해보자.

가장 긴 바이토닉 부분 수열의 공식(?)이라고 한다면

"(정방향 LIS + 역방향 LIS)의 최댓값 - 1"

이라고 할 수 있겠다.

입력이 아래와 같이 주어진다면

1 5 2 1 4 3 4 5 2 1

A[]는 입력된 수열을 저장한다.

DP[] 상태를 보면 아래와 같다.

DP[N]은 N까지의 수열이 주어질 때, 최대 부분 증가수열의 길이를 저장한다.

여기서 정방향 LIS, 역방향 LIS 의 각 index에 해당하는 해를 더한 결과는 아래와 같다.

SUM의 최댓값은 8이고, 여기서 1을 빼준 7이 가장 긴 바이토닉 부분 수열이 된다.

Why?!

왜 이렇게 동작시켜야 할까?

바이토닉 수열은 

을 만족해야 한다.

즉, 증가하다가 감소하는 수열이 되어야 한다.

그럼 정방향 LIS를 통해서 증가하는 수열을 알 수 있고,

역방향 LIS를 통해서 감소하는 수열을 알 수 있다.

이 두 결과를 더하면 가장 긴 바이토닉 부분 수열이 만들어지고

중복된 자기 자신을 빼주면 결과를 얻을 수 있다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <cstdio> using namespace std;   int A[1001], DP[2][1001];   int main(void) {     int n, i, j, res = 0;     //freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++) {         scanf("%d", &A[i]);           int tmp = 0;         for (j = 1; j < i; j++) {             if (A[i] > A[j] && DP[0][j] > tmp)                 tmp = DP[0][j];         }           DP[0][i] = tmp + 1;     }       for (i = n; i >= 1; i--) {         int tmp = 0;         for (j = n; j > i; j--) {             if (A[i] > A[j] && DP[1][j] > tmp)                 tmp = DP[1][j];         }           DP[1][i] = tmp + 1;     }       for (i = 1; i <= n; i++) {         int sum = DP[0][i] + DP[1][i];         if (sum > res)              res = sum;     }       printf("%d\n", res - 1);       return 0; } Colored by Color Scripter

cs

line 11~21) 정방향 LIS를 먼저 구해준다.

line 23~31) 역방향 LIS 구하기

line 33~37) 가장 긴 바이토닉 부분 수열의 길이 구하기

line 39) 중복된 자기 자신을 빼줌

#. Other Code

#include <cstdio>
using namespace std;
 
int A[1001], DP[2][1001];
 
int main(void)
{
    int n, i, j, res = 0;
    //freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
 
        int tmp = 0;
        for (j = 1; j < i; j++) {
            if (A[i] > A[j] && DP[0][j] > tmp)
                tmp = DP[0][j];
        }
 
        DP[0][i] = tmp + 1;
    }
 
    for (i = n; i >= 1; i--) {
        int tmp = 0;
        for (j = n; j > i; j--) {
            if (A[i] > A[j] && DP[1][j] > tmp)
                tmp = DP[1][j];
        }
 
        DP[1][i] = tmp + 1;
        if (DP[0][i] + DP[1][i] - 1 > res)
            res = DP[0][i] + DP[1][i] - 1;
    }
 
    printf("%d\n", res);
 
    return 0;
}

line 31~32) 가장 긴 바이토닉 부분 수열의 길이를 역방향 LIS를 구하는 과정에서 같이 구해주면서

최적화할 수 있다.