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

문제

문제 분석

DP문제이다.

우선 증가하는 부분수열과 감소하는 부분수열로 문제로 나누어 보았다.

그 결과가 (1,2,3,2,1)이라고 가정하자. 그렇다면 "3"을 갖는 인덱스를 기준으로 양 옆으로 나뉠것이다.

물론 3이 여러개일 수도 있고 위치마다 결과는 다르지만 최적의 값을 도출하는 인덱스를 X라고 가정하자.

결과가 가장 긴 바이토닉 수열이 되기 위해서는 (X번째 인덱스 이전을 기준으로 증가하는 수열 + X번째 인덱스 이전을 기준으로 감소하는 수열)이 최대가 되는 경우일 것이다.

그렇다면 모든 인덱스 i에 대하여 해당 인덱스 전까지의 증가하는 수열과 i이후의 감소하는 수열의 길이를 구하고 모든 인덱스에 대하여 비교하면 될것이다.

그렇다면 증가 / 감소하는 수열을 어떻게 구하는지 알아보기에 앞서 우선 우리가 사용할 변수들이 갖는 의미를 명확하게 하고가자

DP[i] = 최대 증가수열의 길이가 i일때 그 길이를 갖는 수열의 원소 중 최댓값

max_count = 현재 증가수열의 최대길이

만약 DP[max_count] < input[i]이라면 이전의 증가수열에 붙일 수 있다는 의미이므로  DP[++max_count] = input[i]로 max_count를 하나 증가시키고, 그곳에 input[i]를 저장한다.

만약 그렇지 않다면 DP에서 input[i]보단 큰 값중 가장 가까운 원소를 구한다. 그리고 그것을 input[i]로 갱신한다.

이렇게 하는 이유는 DP의 정의때문인데, DP가 길이가 I인 부분 증가수열 중에서 가장 마지막값을 저장하는 원소인데, 더 최적의 값으로 대체할 수 있기 때문이다. (예시 : [1 2 100 3], 여기서 길이가 3인 부분 증가 수열 중, 최소 마지막 원소값은 100이 아닌 3)

감소하는 수열을 0~N-1의 순이 아닌 N-1~0순으로 보면 증가하는 수열이므로 DP_2에 대해서 똑같이 작업하면 된다.

그리고 이렇게 나타난 값을 바탕으로 DP[i] + DP_2[i] - 1의 최댓값을 찾는 것이다.

-1을 해준 이유는 최적의 바오토닉 수열에선 반드시 하나의 최댓값 원소를 공유할 것이기 때문이다.

하지만 이런 의문이 들 수 도 있다. "증가하는 수열의 최댓값과 감소하는 수열에서의 최댓값이 다르기 때문에 -1을 하면 안되지 않을까?" 하지만 그런 경우는 어차피 최적이 아니고, 이후 두 부분수열의 최댓값이 같은 지점에서 반드시 다시 만날것이기 때문에 이처럼 연산해도 된다.

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;
void solution()
{
    // code
    int n;
    int max_count = 0;  
    cin >> n;
    vector<int> input_v;
    vector<int> dp;
    vector<int> dp_2;
    vector<int> dp_2_count;
    vector<int> dp_2_max;

    for(int i=0; i<n; i++)
    {
        int a;
        cin >> a;
        input_v.push_back(a);
        dp.push_back(MY_INT_MAX);
        dp_2.push_back(MY_INT_MAX);        
        dp_2_count.push_back(MY_INT_MAX);
        dp_2_max.push_back(MY_INT_MAX);        
    }
    dp[0] = input_v[0];

    int max_count_2 = 0;
    dp_2[0] = input_v[dp_2.size()-1];
    dp_2_count[dp_2.size()-1] = 1;
    dp_2_max[dp_2.size()-1] = input_v[dp_2.size()-1];

    for(int i=input_v.size()-2; i>=0; i--)
    {
        if(dp_2[max_count_2] < input_v[i])
            dp_2[++max_count_2] = input_v[i];

        vector<int>::iterator it = lower_bound(dp_2.begin(), dp_2.end(), input_v[i]);
        if(*it != input_v[i])
            *it = input_v[i];
        int tmp_idx = i;
        dp_2_count[tmp_idx] = max_count_2 + 1;
        dp_2_max[tmp_idx] = dp_2[max_count_2];        
    }

    int output = 0;
    for(int i=1; i<input_v.size(); i++)
    {
        if(dp[max_count] < input_v[i])
            dp[++max_count] = input_v[i];

        vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), input_v[i]);
        if(*it != input_v[i])
            *it = input_v[i];
        if (dp[max_count] == dp_2_max[i])
        {
            output = max(output, max_count + dp_2_count[i] - 1);
        }
        else if(dp[max_count] > dp_2_max[i])
        {
            output = max(output, max_count + dp_2_count[i]);
        }
    }

    cout << output + 1;
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

너무 변수가 많았다. 다른사람의 코드를 보니 부분수열의 길이를 저장하는 배열 2개와 그 길이를 연산하기 위한 배열(나의 DP배열)하나를 더해서 총 3개의 배열만 사용해도 풀 수 있었다.

그리고 위에 언급한 대로 "증가하는 수열의 최댓값과 감소하는 수열에서의 최댓값이 다르기 때문에 -1을 하면 안되지 않을까?"라는 의문때문에 길이 뿐만 아니라 그 길이에서 최댓값을 갖는 원소까지 저장하고 그것을 비교하다보니 좀 복잡해진것 같다.

그냥 간결하게 증가수열, 감소수열 2개만 구하고 두개의 합-1만 해도 끝이었다.

코테였다면 시간을 너무 많이 잡아먹었을것같다.