백준, BOJ, 11054번, 가장 긴 바이토닉 부분 수열 : C++ [CPP]

증가수열을 어떻게 구하는지 알면 바로 푼다.

 

 

 

 

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

 

---

 

#맞은 풀이

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 1001;

int N;

int arr[MAX];
int dp[2][MAX];//0번째 정방향, 1번째 역방향 증가수열.

int main(){
    cin >> N;
    
    fill(dp[0], dp[0]+MAX, 1); //최소한 자기 자신을 포함하는 1의 길이를 가짐
    fill(dp[1], dp[1]+MAX, 1); //최소한 자기 자신을 포함하는 1의 길이를 가짐
    
    for(int i = 1; i<=N; i++){
        cin >> arr[i];

    }

    //dp[0][N]은 N번째 원소를 마지막으로 하는 증가 수열의 길이를 말함
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<i; j++){
            if(arr[j]<arr[i]){
                dp[0][i] = max(dp[0][i], dp[0][j] + 1);
            }
        }
    }
    
    
    //임의의 위치의 K부터 감소수열의 를 찾게해야함.
    //즉, dp[1][K]는 K부터 시작하는 감소 수열의 길이임.
    //이는 반대로 N부터 K를 원소로 가지는 증가 수열을 알아내면 됨.
    for(int i = N; i>=1; i--){
        for(int j = N; j>i; j--){
            if(arr[j]<arr[i]){
                dp[1][i] = max(dp[1][i], dp[1][j] + 1);
            }
        }
    }
    int ans = 0;
    //N개 후보 중 가장 최댓값
    // 1. 정방향(K번째를 마지막 원소를 하는 증가수열길이)
    // 2. 역방향(K번째를 마지막 원소로 하는 증가수열 길이)
    for(int k = 1; k<=N; k++){
        ans = max(ans, dp[0][k] + dp[1][k]); 
    }
    
    cout << ans-1; //K번째는 중복으로 세어줬기 때문에 1을 뺌
    
    return 0;
}

 

 

DP의 가장 기본적인 문제라고 볼 수 있고 그냥 수학적인 머리로 감소수열을 거꾸로하면 증가수열이네?

라고 생각하면 바로 풀린다.

 

for문이 중첩된 것은 1000 * 1000 밖에 안되기 때문에 이렇게 Brute Force 같이 풀었다.

역으로 정말 K부터 시작하는 감소수열을 찾는 것이었다면.. 계속 갱신되어서 복잡하게 됐을 것이다.

역방향으로 증가수열을 찾았기에 그나마 쉽게 풀 수 있었다.