[백준] 11053번: 가장 긴 증가하는 부분 수열 - java

문제

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

11053번: 가장 긴 증가하는 부분 수열

 

접근법

이런 문제를 최장 증가 부분 수열(LIS)라고 한다. 그냥.. 나중에 아는척 하면 간지나는 상식!ㅎ.ㅎ

 

문제에 있는 예시를 그대로 따라해보다 보면 어떠한 방식으로 풀어야 될지 감이 온다. A[0]부터 A[5]까지 자기 자신까지의 최장 길이를 구해보자. 일단, 모두 적어도 가장 긴 증가하는 부분 수열의 길이는 1이다. (자기자신!)

 

A[0]: 자신 보다 작은 수가 없기 때문에 A[0]까지의 최장 길이는 1이다.

A[1]: A[0]이 자기 자신보다 작기 때문에 A[1]까지의 최장 길이는 2이다.

A[2]: 자신 보다 작은 수가 없기 때문에 A[2]까지의 최장 길이는 1이다.

A[3]: A[0], A[1], A[2] 모두 자기 자신보다 작지만 A[1]까지의 길이가 가장 기므로 A[3]까지의 최장 길이는 A[1] + 1 = 3이다.

 

이제 어느 정도 감을 잡았을 것이다.

 

점화식

위 예시를 바탕으로 점화식을 구해보자

dp[i] = dp[i]까지의 증가 하는 부분 수열 중 가장 긴 길이
dp[i] = A[0] ~ A[i - 1] 중 A[i] 보다 작은 수의 집합을 B라고 할 때, max(dp[B[0]]..) + 1

매번 자신 보다 인덱스 값이 작은 수들을 탐색해야 하므로 시간 복잡도는 $O(N^2)$ 이다. N의 범위가 최대 1,000이므로 괜찮다.

 

코드

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

public class Main {

    static int N;
    static int[] A;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        A = new int[N];
        dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int max = 1;
        dp[0] = 1;
        for (int i = 1; i < N; i++) {
            dp[i] = 1; // 적어도 길이는 1이다.

            for (int j = 0; j < i; j++) {
                if (A[j] < A[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

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

        System.out.println(max);
    }
}