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

---

0. 문제

 

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

 

1. 아이디어

 

1) i번째 원소를 기준으로, (왼쪽) arr[0] ~ arr[i]는 증가수열, (오른쪽) arr[i] ~ arr[N-1]은 감소수열

 

2) 따라서 각각의 원소가 가질 수 있는 증가수열과 감소수열의 길이를 합했을 때 가장 큰 길이를 구한다!

 

3) 이때, 주의할 건 감소수열의 길이를 구할 때 반!드!시! i번째 원소를 포함하는 길이여야 한다는 것!

 

4) 그래서 나는 역으로, arr[N-1] ~ arr[i]까지의 증가수열의 길이를 구하기로 했다.

 

2. 소스코드

 

#include <iostream>
#include <memory.h>
int main()
{
    int N, result = 0, arr[1000], inc[1000], dec[1000];
    memset(dec, -1, sizeof(dec));
    std::cin >> N;
    for (int i = 0; i < N; i++)
        std::cin >> arr[i];
 
    for (int i = 0; i < N; i++)
    {
        int maxi = 0;
        for (int j = 0; j < i; j++) // 증가수열의 길이
            if (arr[j] < arr[i]) // 자기보다 작은 값일 때
                if (inc[j] > maxi) maxi = inc[j];
        inc[i] = maxi + 1; // i번째 원소의 최대 증가수열의 길이
 
        if (dec[i] == -1)
        {
            for (int j = N - 1; j >= i; j--) //i번째 원소를 반드시 포함하는 감소수열!
            {
                int maxd = 0;
                for (int k = N - 1; k > j; k--)
                    if (arr[k] < arr[j])
                        if (dec[k] > maxd) maxd = dec[k];
                dec[j] = maxd + 1;
            }
        }
        //0번째 원소의 감소수열 길이를 구하기 위해서는
        //1~N-1번째 원소의 감소수열 길이를 어차피 다 구해야 한다. 이때 메모이제이션을 이용!
 
        int temp = inc[i] + dec[i] - 1;
        //증가수열과 감소수열의 길이를 구할 때 각각 i번째 원소를 포함했으니 중복되어서 길이에 -1을 해줘야 한다!
        if (temp > result) result = temp;
    }
    std::cout << result;
}

 

3. 결과

 

 

4. 피드백

 

• 힘들었다.. 그래도 골드 문제를 풀어서 뿌듯

• 배열 인덱스를 마음대로 다루는 건 어렵다 ㅠㅠ 헷갈리지만 손으로 따라가면서 해야겠다

---