11054 - C (dp, LIS)

11054 가장 긴 바이토닉 부분 수열은 LIS를 양쪽으로 한 다음, 마지막에 더해주는 과정만 취하면 해결할 수 있는 간단한 문제였다. 11053 가장 긴 부분 증가하는 수열 문제의 코드에서 약간의 수정을 더하여 문제를 풀었다.

문제는 이렇게 나와있고, 입력값이 1000까지라는 점을 감안하여 배열 자체를 1001가지로 할당해서 사용했지만, 만약 space complexity를 줄이는 방향으로 사용하고 싶다면, 이렇게 하면 안되긴 한다. 이미 입력값 N을 통해 얼마 크기의 공간이 필요한지는 확인이 가능하기 때문이다.

기준점이 중요하다는 사실을 까먹은 채 왜 계속해서 값이 안나오지 하고 있었다. 중요한 것은 기준점!!! 이를 기준으로 바이토닉 수열인지 아닌지를 확인하며, 더한 값을 비교해야한다는 점을 문제를 통해 기억하고 있어야 했다.

step 1. 왼쪽에서 부터 증가하는 가장 긴 수열의 값을 Left 배열에 저장해나간다.
step 2. 오른쪽에서 부터 증가하는 가장 긴 수열의 값을 Right 배열에 저장해 나간다.
step 3. 특정 항을 기준으로 증가하는 수열의 값을 확인하는 매커니즘이기 때문에 반복문을 통해, 더한 값 - 1의 MAX값을 int maxBitonic에 비교하며 저장한 후 출력한다.

#include <stdio.h>
// bitonic sequence

int arr[1001] = {0};
int left[1001] = {0};
int right[1001] = {0};
int bitonic[1001] = {0};

int MAX(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int main(void) {
    int N;
    int i;
    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

    // left 구하기
    left[0] = 1;
    for (i = 1; i < N; i++) {
        left[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                left[i] = MAX(left[i], left[j] + 1);
            }
        }
    }

    // right 구하기
    right[N - 1] = 1;
    for (i = N - 2; i >= 0; i--) {
        right[i] = 1;
        for (int j = N - 1; j > i; j--) {
            if (arr[i] > arr[j]) {
                right[i] = MAX(right[i], right[j] + 1);
            }
        }
    }

    int max_L = 0;
    int max_R = 0;

    for (i = 0; i < N; i++) {
        if (max_L < left[i]) {
            max_L = left[i];
        }
    }

    for (i = N - 1; i >= 0; i--) {
        if (max_R < right[i]) {
            max_R = right[i];
        }
    }

  int maxBitonic = 0;
  for (int i = 0; i < N; i++) {
    maxBitonic = MAX(maxBitonic, left[i] + right[i] - 1);
  }

    printf("%d\n", maxBitonic); // 중복되는 가운데 요소를 빼줌

    return 0;
}