가장 긴 증가하는 부분 수열

문제 정보

• 백준 실버 2
• DP
• 문제 링크

풀이

dp[i]를 arr[i]를 마지막 원소로 하는 가장 긴 증가하는 부분 수열의 길이로 정의한다.

현재 값 이전의 값들 중 현재 값보다 작은 값의 개수를 구하는 것으로 구할 수 있다. 즉, 점화식은 다음과 같다.

dp[i] = max(dp[j]) + 1, i > j & arr[i] > arr[j]

이 경우 구현에 이중 for문을 사용해야 하므로 시간복잡도는 $O(n^2)$이 된다.

이진탐색을 쓰면 $O(n\log n)$ 으로도 풀 수 있으나, 이 문제의 경우 $n$이 최대 1000이기에 $O(n^2)$으로도 괜찮다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());            
        
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        
        int answer = -1;
        for (int i = 0; i < n; i++)
            answer = Math.max(answer, dp[i]);
        
        System.out.println(answer);
    }
}