백준 11054 가장 긴 바이토닉 부분 수열 Java: 양방향 LIS DP

백준 11054번 ‘가장 긴 바이토닉 부분 수열’은 어떤 peak까지 strictly increasing하고, 그 뒤 strictly decreasing하는 부분 수열의 최대 길이를 구한다. 각 index를 peak로 가정해 왼쪽에서 끝나는 LIS와 오른쪽으로 시작하는 감소 수열 길이를 더하면 된다.

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

두 DP 배열의 의미

• increasing[i]: values[i]에서 끝나는 가장 긴 증가 부분 수열
• decreasing[i]: values[i]에서 시작하는 가장 긴 감소 부분 수열

두 값 모두 자기 자신을 포함하므로 1로 시작한다.

increasing[i]
= max(increasing[j] + 1), j < i and values[j] < values[i]

decreasing[i]
= max(decreasing[j] + 1), j > i and values[j] < values[i]

index i를 peak로 합칠 때 자기 자신이 두 배열에 모두 들어 있으므로 한 번 뺀다.

bitonic length at i = increasing[i] + decreasing[i] - 1

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int count = Integer.parseInt(reader.readLine());
        int[] values = new int[count];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        for (int index = 0; index < count; index++) {
            values[index] = Integer.parseInt(tokenizer.nextToken());
        }

        int[] increasing = new int[count];
        int[] decreasing = new int[count];
        Arrays.fill(increasing, 1);
        Arrays.fill(decreasing, 1);

        for (int current = 0; current < count; current++) {
            for (int previous = 0; previous < current; previous++) {
                if (values[previous] < values[current]) {
                    increasing[current] = Math.max(
                            increasing[current],
                            increasing[previous] + 1
                    );
                }
            }
        }

        for (int current = count - 1; current >= 0; current--) {
            for (int next = current + 1; next < count; next++) {
                if (values[next] < values[current]) {
                    decreasing[current] = Math.max(
                            decreasing[current],
                            decreasing[next] + 1
                    );
                }
            }
        }

        int answer = 0;
        for (int peak = 0; peak < count; peak++) {
            answer = Math.max(
                    answer,
                    increasing[peak] + decreasing[peak] - 1
            );
        }

        System.out.println(answer);
    }
}

증가만 하거나 감소만 해도 바이토닉이다

문제 정의에서는 증가 부분이나 감소 부분의 길이가 1이어도 된다. 따라서 완전히 증가하는 수열은 마지막 값을 peak로, 완전히 감소하는 수열은 첫 값을 peak로 잡아 전체 길이가 답이 된다.

같은 값은 strictly increasing·decreasing 관계가 아니므로 비교에 <를 사용한다. 중복 값이 있어도 sequence index는 유지되며 같은 값끼리는 길이를 늘리지 않는다.

LIS 직후 10~20분 만에 푼 기록

원문에는 백준 11053 LIS를 약 3시간 만에 푼 직후 이 문제를 만나 10분 또는 20분 만에 응용했다고 적혀 있다. 처음 구현은 increasing 길이에만 자기 자신을 포함하고 decreasing은 0에서 시작해 두 값을 그대로 더했다.

그 방식도 일관되게 쓰면 맞지만, 두 배열을 모두 “현재 원소를 포함한 길이”로 정의하고 마지막에 1을 빼는 표준 형태가 상태를 설명하기 쉽다. 시간 복잡도는 두 번의 이중 loop로 O(N²), 공간은 O(N)이다.

검증 범위

Java source를 수동 검토하고 all-increasing, all-decreasing, duplicate, peak가 양끝인 경우와 작은 random sequence를 모든 subsequence brute force와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.