99클럽 코테 스터디 32일차 TIL + DP(C++)

문제

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

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

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    int lis[1001];
    int lds[1001];
    int nums[1001];
    int ans[1001];

    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        lis[i] = 1;
        lds[i] = 1;
    }

    // 기준값을 마지막으로 증가하는 부분 수열
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j])
                lis[i] = max(lis[i], lis[j] + 1);
    }

    // 기준값부터 감소하는 부분 수열
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (nums[i] > nums[j])
                lds[i] = max(lds[i], lds[j] + 1);
        }
    }

    for (int i = 0; i < n; i++) {
        ans[i] = lis[i] + lds[i] - 1;
    }

    cout << *max_element(ans, ans + n);

    return 0;
}

 

풀이

가장 긴 바이토닉 부분 수열의 길이

= 기준값 i까지 가장 긴 증가하는 부분 수열의 길이 + 기준값 i부터 가장 긴 감소하는 부분 수열의 길이 - 1

 

(증가하는 부분 수열과 감소하는 부분 수열에서 기준값 i가 중복되므로 마지막에 1을 뺄셈함)