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

문제 링크입니다: https://www.acmicpc.net/problem/11054

최근에 자주 풀었던 LIS의 응용문제였습니다.

http://jaimemin.tistory.com/317와 다른점이라면 기존에는 해당 인덱스를 시작으로 하는 최대 부분수열의 길이를 캐시에 저장했는데 이 문제에서는 해당 인덱스를 마지막 요소로 하는 최대 부분수열의 길이를 캐시에 저장해야했다는 점입니다.

_{우선 정방향 LIS를 구하고 캐시에 저장한 뒤 반대방향 LIS를 구하고 캐시에 저장했습니다.}

_{그 다음 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 를 만족해야하므로 모든 인덱스를 순회하며 fCache[i]+rCache[i]의 최대값을 찾았습니다.}

여기서 주의할 점은 i번째 인덱스에 있는 숫자가 중복이 되므로 결과에서 -1을 해야했다는 점입니다!

/*

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk - 1 < Sk > Sk + 1 > ... SN - 1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, { 10, 20, 30, 25, 20 }과{ 10, 20, 30, 40 }, { 50, 40, 25, 10 } 은 바이토닉 수열이지만,

{ 1, 2, 3, 2, 1, 2, 3, 2, 1 }과{ 10, 20, 30, 40, 20, 30 } 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000;

 

int N;

int arr[MAX];

int fCache[MAX], rCache[MAX]; //frontLISCache, rearLISCache

 

//기존에 작성한 LIS는 해당 인덱스로부터 시작한 LIS의 길이를 cache에 저장

//하지만 이 문제에서는 해당 인덱스를 마지막으로 하는 LIS의 길이를 cache에 저장

void frontLIS(void)

{

        for (int i = 0; i < N; i++)

        {

               fCache[i] = 1; //자기자신 포함

               for (int j = 0; j <= i; j++)

                       if (arr[i] > arr[j] && fCache[j] + 1 > fCache[i])

                              fCache[i] = fCache[j] + 1;

        }

}

 

//뒤에서부터 LIS

void rearLIS(void)

{

        for (int i = N - 1; i >= 0; i--)

        {

               rCache[i] = 1; //자기자신 포함

               for (int j = N - 1; j >= i; j--)

                       if (arr[i] > arr[j] && rCache[j] + 1 > rCache[i])

                              rCache[i] = rCache[j] + 1;

        }

}

 

int main(void)

{

        cin >> N;

        if (N<1 || N>MAX)

               exit(-1);

 

        for (int i = 0; i < N; i++)

               cin >> arr[i];

       

        frontLIS();

        rearLIS();

        int result = fCache[0] + rCache[0];

        for (int i = 1; i < N; i++)

        {

               int candidate = fCache[i] + rCache[i];

               if (result < candidate)

                       result = candidate;

        }

        cout << result - 1 << endl; //두 캐시의 합이 최대인 인덱스에서 중복

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~