[백준/C언어] 11054번 - 가장 긴 바이토닉 부분 수열

백준 웹사이트 "11054번 - 가장 긴 바이토닉 부분 수열" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

11054번: 가장 긴 바이토닉 부분 수열

---

소스 코드

#include <stdio.h>

int max(int a, int b);

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

    //1. 양쪽으로 LIS의 배열 구하기
    int LIS_left[N]; //LIS_left[i]: 왼쪽부터, A[i]를 포함하는 LIS의 길이
    int LIS_right[N]; //LIS_right[i]: 오른쪽부터, A[i]를 포함하는 LIS의 길이

    LIS_left[0]=1;
    LIS_right[N-1]=1;
    for(int i=1; i<N; i++){
        LIS_left[i]=1;
        LIS_right[N-1-i]=1;
        for(int j=0; j<i; j++){
            if(A[i]>A[j])
                LIS_left[i] = max(LIS_left[i], LIS_left[j]+1);
            if(A[N-1-i]>A[N-1-j])
                LIS_right[N-1-i] = max(LIS_right[N-1-i], LIS_right[N-1-j]+1);
        }
    }
    /*
    for(int i=0; i<N; i++){
        printf("LIS_left[%d]: %d, LIS_right[%d]: %d\n", i, LIS_left[i], i, LIS_right[i]);
    }
    */


    //2. 둘을 합쳐 바이토닉 수열의 배열 구하기
    int bitonic[N];
    for(int i=0; i<N; i++){
        bitonic[i] = LIS_left[i] + LIS_right[i]-1;
        //printf("bitonic[%d]: %d\n", i, bitonic[i]);
    }

    //3. 가장 긴 바이토닉 수열의 길이 구하기
    int max=0;
    for(int i=0; i<N; i++){
        if(bitonic[i]>max)
            max = bitonic[i];
    }
    printf("%d\n", max);
}

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

---

문제 풀이

  이전 문제 "11053번 - 가장 긴 증가하는 부분 수열"를 응용하는 문제입니다. LIS는 Longest Increasing Subsequence로, 가장 긴 증가하는 부분수열이었죠? 이번 문제의 Bitonic Subsequence는 증가하다가 감소하는 부분수열입니다. 증가하는 부분수열과 감소하는 부분수열을 이어붙인 것과도 같으므로, 'Bitonic Subsequence = Increasing Subsequence + Decreasing Subsequence' 이라고 볼 수 있겠죠. 가능한 여러가지 Bitonic Subsequence 중 가장 긴, Longest Bitonic Subsequence를 구하는 것이 이번 문제입니다. LIS를 구하는 방법을 모르시는 분들은, 이전 문제를 참고해주세요!

[백준/C언어] 11053번 - 가장 긴 증가하는 부분 수열

  그럼, 본격적으로 문제풀이를 알아봅시다. 앞서, 'Bitonic Subsequence = Increasing Subsequence + Decreasing Subsequence' 라는 표현을 이용했습니다. 증가하는 부분수열과 감소하는 부분수열의 사이에, 반드시 '가장 큰 수'가 한 개 존재하고, 이 수의 왼쪽으로 증가하는 부분수열, 오른쪽으로 감소하는 부분수열이 위치합니다. 각각의 부분수열이 최대 길이라면, 이 수가 가장 큰 수인 바이토닉 부분수열 중, 가장 큰 부분수열이 되겠죠?

  이 수를 A[i]라고 하고, 다시 한 번 봅시다. A[i]의 왼쪽에 위치한 증가하는 부분수열이 'A[i]를 포함하고, A[i]가 최대인 가장 긴 증가하는 부분수열'이 되도록 하고 싶습니다. 공교롭게도, 이는 이전 문제에서 구한 LIS 배열의 정의와 똑같기에 같은 방식으로 구할 수 있습니다.

  A[i]의 오른쪽에 위치한 감소하는 부분수열도 마찬가지로, 'A[i]를 포함하고, A[i]가 최대인 가장 긴 감소하는 부분수열'이 되도록 하고 싶습니다. 이것도 LIS를 이용할 수만 있다면, 코드가 굉장히 간단해지겠죠? 그 방법은 바로 수열 A의 오른쪽에서부터 역순으로 LIS를 구하는 것입니다. 오른쪽부터, A[i]를 포함하는 LIS를 구하면 되는 셈이죠.

  이런 식으로 문제를 나누어 풀면, A[i]를 최댓값으로 가지는 가장 긴 바이토닉 부분수열을 구하는 문제는 LIS를 두 번 구하는 문제로 단순화됩니다. 이러한 논리로, Line 13 ~ 28 에서는 왼쪽부터의 LIS 배열인 'LIS_left'와 오른쪽부터의 LIS 배열인 'LIS_right'를 구합니다.

  이렇게 'LIS_left'와 'LIS_right'를 구하면, Line 37 ~ 41에서는 이 둘을 합쳐 새로운 배열 'bitonic'을 구합니다. 이는 각 수를 최대 수로 할 경우의 최대 바이토닉 부분 수열의 길이를 의미하므로, LIS_left[i]와 LIS_right[i]를 더한 후 1 만큼 빼주면 됩니다. 1 만큼 빼주는 것은 '최대 수'인 A[i]가 LIS_left[i]와 LIS_right[i]에서 중복되기 때문입니다.

  마지막으로, 가장 긴 바이토닉 부분수열의 길이는 배열 bitonic의 모든 요소들 중 최댓값을 구하면 됩니다 (Line 43 ~ 50). 이렇게, 다소 복잡해보이는 '가장 긴 바이토닉 부분 수열의 길이' 문제를 이미 알고 있는 'LIS 구하기' 문제로 단순화시켜 깔끔하게 문제를 풀 수 있습니다.