[BOJ 11054번/C++] 가장 긴 바이토닉 부분 수열

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

가장 긴 바이토닉 부분 수열

문제

문제

수열 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

제한사항

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

풀이

이전에 풀었던 가장 긴 증가하는 부분 수열과 비슷한 문제였다.

이전의 가장 긴 증가하는 부분 수열에서 두 가지 조건이 추가 된다.

 

뒤로 갈수록 수가 점점 작아진다.

또는, 한 수를 기준으로 앞으로는 점점 커지는 수열이, 뒤로는 점점 작아지는 수열이 온다.

#include <iostream>

using namespace std;

int dp[2][1001];
int arr[1001];

int main() {
    int N;
    cin >> N;
    int answer = 0;

    for (int i = 0; i < N; i++) {
        cin >> arr[i + 1];
    }

    // 앞에서 부터 점점 커지는 수열
    for (int i = 1; i <= N; i++) {
        dp[0][i] = 1;

        for (int j = 1; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[0][i] = max(dp[0][i], dp[0][j] + 1);
            }
        }
    }

    // 앞에서 부터 점점 작아지는 수열
    for (int i = N; i > 0; i--) {
        dp[1][i] = 1;

        for (int j = i; j <= N; j++) {
            if (arr[j] < arr[i]) {
                dp[1][i] = max(dp[1][i], dp[1][j] + 1);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        answer = max(answer, dp[0][i] + dp[1][i] - 1);
    }

    cout << answer << endl;
    
    return 0;
}