[백준] 11053번 : 가장 긴 증가하는 부분 수열 (JAVA)

1. 문제 분석

 

오름차순이 되는 부분 수열중에 가장 긴 수열의 길이를 구하면 된다. A의 크기가 1000이라 가장 긴 수열을 직접 구해도 될거같은데, 근데 알고리즘이 DP로 분류되어 있어 DP로 풀었다.

 

시간복잡도 : O(N^2) 

알고리즘 : DP

2. 문제 풀이

수열을 부분적으로 잘라서 부분수열들에서 한 항씩 추가해 가면서 최대 길이를 구한다.

• arr[j] > arr[i] : 더 큰 값을 발견
  
  • dp[i] = Math.max(dp[i], dp[j]+1)
• 더 큰값이 아닐때
  
  • j++

이렇게 부분수열로 쪼개 작은 수열부터 최고 길이를 구해가면 된다.

3. 코드 구현

import java.io.InputStreamReader;
import java.util.Scanner;

public class BOJ_11053 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] num = new int[N+1];
        int[] dp = new int[N+1];

        for(int i = 1; i <= N; i++){
            num[i] = sc.nextInt();
            dp[i] = 1;
        }
        sc.close();

        int answer = 1;
        for(int i = 2; i <= N; i++){
            for(int j = 1; j < i; j++){
                if(num[j] < num[i]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);

    }
}