백준 11053 LIS Java: O(N²) 동적 계획법의 상태 정의

백준 11053번 ‘가장 긴 증가하는 부분 수열’은 원래 순서를 유지하면서 값이 strictly increasing하는 부분 수열의 최대 길이를 구한다. N ≤ 1,000이므로 각 원소 앞의 모든 후보를 확인하는 O(N²) DP로 충분하다.

• 백준 11053번 가장 긴 증가하는 부분 수열

dp[i]는 i에서 끝나야 한다

상태를 “i번째까지 본 전체 LIS”로 잡으면 다음 값과 어떻게 연결할지 정보가 부족하다. 대신 다음처럼 제한한다.

dp[i] = values[i]를 마지막 원소로 반드시 포함하는 LIS 길이

앞 index j < i 중 values[j] < values[i]인 원소 뒤에만 현재 값을 붙일 수 있다.

dp[i] = max(dp[j] + 1)
        where j < i and values[j] < values[i]

붙일 이전 원소가 없어도 자기 자신 하나로 길이 1의 부분 수열을 만들 수 있으므로 모든 dp[i]를 1로 시작한다. 최종 답은 특정 마지막 index가 정해져 있지 않으므로 전체 dp의 최댓값이다.

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[] dp = new int[count];
        Arrays.fill(dp, 1);
        int answer = 1;

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

            answer = Math.max(answer, dp[current]);
        }

        System.out.println(answer);
    }
}

부분 수열은 연속일 필요가 없다

subsequence는 원래 index 순서만 유지하면 중간 원소를 건너뛸 수 있다. substring이나 subarray처럼 연속 구간을 고르는 문제가 아니다. 같은 값은 “증가”가 아니므로 <=가 아니라 <를 사용한다.

이중 loop의 비교 횟수는 대략 N(N-1)/2다. N = 1,000이면 약 50만 번이므로 제한 안에서 충분하다. 전체 시간은 O(N²), 공간은 O(N)이다. 더 큰 입력에서 길이만 필요하면 lower bound를 쓰는 백준 12015 O(N log N) LIS를 검토할 수 있다.

몇 분 만에 만든 점화식을 세 시간 돌아간 기록

원문에는 점화식을 금방 구했지만 시간 복잡도가 터질 것 같아 정답 접근을 스스로 배제했고, 2차원 배열과 comparator 정렬까지 시도하다 약 3시간 뒤 돌아왔다고 적혀 있다. 처음부터 입력 제한에 이중 loop 횟수를 대입했다면 약 499,500번이라는 값을 확인할 수 있었다.

또 int[]의 기본값 0을 그대로 쓰면 자기 자신만 있는 길이 1을 놓친다는 점을 강조했다. DP에서는 language 기본값이 아니라 상태의 의미에 맞는 base case를 먼저 넣어야 한다.

이 LIS를 peak 양쪽에 적용하는 문제는 백준 11054 바이토닉 부분 수열, 전깃줄의 교차하지 않는 최대 집합으로 해석하는 문제는 백준 2565 전깃줄에서 이어진다.

검증 범위

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