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

주어진 수열에서 가장 길게 증가하는 부분 수열의 길이를 구하는 문제다.

 

수열에 주어진 각 숫자의 관점에서 최대 길이를 구해보면 다음과 같다.

1. 전체 수열이 A = {10} 으로 주어진 경우
   최대 길이는 L = { 1} 이다.
    
2. 전체 수열이 A = {10, 20} 으로 주어진 경우
   최대 길이는 L = { 1,  2} 이다.
   
3. 전체 수열이 A = {10, 20, 10} 으로 주어진 경우
   최대 길이는 L = { 1,  2,  1} 이다.
   
4. 전체 수열이 A = {10, 20, 10, 30} 으로 주어진 경우
   최대 길이는 L = { 1,  2,  1,  3} 이다.
   
5. 전체 수열이 A = {10, 20, 10, 30, 20} 으로 주어진 경우
   최대 길이는 L = { 1,  2,  1,  3,  2} 이다.
   
6. 전체 수열이 A = {10, 20, 10, 30, 20, 50} 으로 주어진 경우
   최대 길이는 L = { 1,  2,  1,  3,  2,  4} 이다.

 

마지막 최대 길이 L을 보면 하나의 규칙을 알 수 있는데, L은 각 숫자의 관점에서 볼 때 좌측에 나열된 숫자 중 자신보다 작은 숫자의 개수에 1을 더한 값이라는 것이다.

 

A = {10, 20, 10, 30, 20, 50} 에서

첫 번째 10보다 좌측에 있으면서 작은 숫자의 개수는 0이며,
두 번째 20보다 좌측에 있으면서 작은 숫자의 개수는 1,
... 을 하게 되면

작은 숫자의 개수 = {0, 1, 0, 2, 1, 3} 을 얻을 수 있다.

 

따라서! 각 숫자를 돌며, 숫자의 좌측에 자신보다 작은 숫자 종류의 수와 자기 자신의 길이(1)를 더한다면, 각 숫자의 관점에서 최대 수열 길이를 구할 수 있다.

 

※ 주의할 점은 각 숫자의 관점에서 좌측에 나열된 숫자 증 자신보다 작은 숫자의 개수만큼 더하는 것이 아니라, 자신보다 작은 숫자의 종류 개수만큼 더하는 것이다.

 

import java.util.Scanner;

public class Main {
    public static void main (String[] args){
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        // 수열 초기화
        int[] seq = new int[N];
        for (int i = 0; i < N; i++) {
            seq[i] = in.nextInt();
        }

        // dp 계산
        int[] dp = new int[N];

        for (int i = 0; i < N; i++) {
            dp[i] = 1; // 자기 자신의 길이

            for (int j = 0; j < i; j++) {
                if (seq[i] > seq[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        
        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
        
    }
}