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

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

문제를 통해 바이토닉 부분 수열에 대해 파악한 점은, ‘가장 긴 증가하는 부분 수열’과 ‘가장 긴 감소하는 부분 수열’이 합쳐진 모양새라는 것이다. 수열에 대해 이렇게 판단하고 나니, 문제 해결의 아이디어를 떠올리는데 어렵지 않았다.

Dynamic Programming

먼저 바이토닉 부분 수열을 구하기 전에, 문제를 쉽게 치환해서 다른 문제 조건이 동일한 ‘가장 긴 증가하는 부분 수열’을 구한다고 생각해보자. 0~k까지 수열에 대해서 증가하는 부분 수열을 구한다. 다음 k+1번째 원소까지 수열에 대해서도 증가하는 부분 수열을 구한다.

이렇게 bottom-up 방식으로 점진적으로 전체 수열에 대해 결과를 구할 수 있기 때문에, 다이나믹 프로그래밍을 이용할 수 있다.

i 번째 원소에서 가장 긴 증가하는 부분 수열 dp[i]는 아래와 같이 구할 수 있다. ‘가장 긴 감소하는 부분 수열’은 배열의 뒤에서부터 스캔하면서 증가하는 부분 수열을 구한다.

• 0번째 원소부터 i - 1번째 원소까지의 dp 중 최댓값에 i번째 원소 하나를 더한 dp[j] + 1
• ‘증가하는’ 조건을 만족해야 하므로 arr[i] > arr[j]

가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 합쳐서, 오름차순과 내림차순이 합쳐진 수열이 완성된다.

문제에 주어진 예시로 원소마다 증가하는 / 감소하는 부분 수열을 구하면 다음과 같다.

count sum이 8인 부분을 보자. 바이토닉 부분 수열에서는 원소 하나가 겹치기 때문에 제외해야 한다.

• 가장 긴 증가하는 부분 수열 : {1, 2, 3, 4, 5}
• 가장 긴 감소하는 부분 수열 : {5, 2, 1}
• 가장 긴 바이토닉 부분 수열 : {1, 2, 3, 4, 5, 2, 1}

cpp 풀이 java 풀이 python 풀이

시간 복잡도

이중 for문으로 dp 값을 구한다. 문제에서 주어진 수열의 크기 N은 1 이상 1000 이하이므로, 가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열 각각 O(N^2) 의 시간 복잡도를 가진다.

// Longest Increasing
static void LIS() {
    for(int i = 0; i < N; i++) {
        left_dp[i] = 1; // me
        for(int j = 0; j < i; j++) {
            if(sequence[i] > sequence[j] && left_dp[i] < left_dp[j] + 1) {
                left_dp[i] = left_dp[j] + 1;
            }
        }
    }
}

각 부분 수열을 구한 후 같은 위치의 수열의 원소들을 더하면서 최댓값을 찾는다. 이 과정에서 O(N)의 시간 복잡도를 가진다.

// Find Largest value
int max_value = 0;
for(int i = 0; i < N; i++) {
    if(max_value < left_dp[i] + right_dp[i]) max_value = left_dp[i] + right_dp[i];
}

최종적으로 2 * O(N^2) + O(N) == O(N^2)으로 해결 가능하고, N이 10의 3승이기 때문에 시간 제한 1초 안에 해결 가능하다.