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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

 

 

 

이 문제는 해결하는데 굉장히 오랜시간이 걸린문제이다 

주어진 수열에서 가장 긴 증가하는 수열을 LIS라고 한다 

LIS를 구하는것은 생각보다 쉽지 않았다 

 

 

알고리즘 설계 

 

1. 이 문제는 LIS의 길이를 출력하라는 문제다 

 

2. 입력값 n에 따라 크기가 n인 list배열과 dp배열을 만든다 

 

list배열: 수열의 요소를 입력받는 배열

dp배열:  현재위치의 수로 끝나는 증가하는 부분 수열중에 가장 긴 것의 길이 

이게 뭔말이냐면?

ex) list= 1,2,3,1,2,5일때

dp[6]= 5로 끝나는 증가하는 부분 수열은 

1 2 3 5

1,2,5 

2개이다 그 중에서 길이가 가장 긴 것은 4이다

dp[6]=4 

 

 

dp[0]은 당연히 1이다

 

 

3. 이제 LIS를 구하는 코드를 작성해볼것이다 

 

예를 들어 크기가 10인 list 배열에 1 100 2 50 60 3 5 6 7 200 이 입력된다면

list    1    100    2      50    60     3      5      6       7     200

dp dp[0] dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] dp[7] dp[8] dp[9]

 

dp[0]=1

dp[1]=(dp[0])+1=2

dp[2]=(dp[0])+1=2

dp[3]=max(dp[0],dp[2])+1=3

dp[4]=max(dp[0],dp[2],dp[3])+1=4

dp[5]=max(dp[0],dp[2])+1= 3

dp[6]=max(dp[0],d[2],dp[5])+1=4

dp[7]=max(dp[0],dp[2],dp[5],dp[6])+1=5

dp[8]=max(dp[0],dp[2],dp[5],dp[6],dp[7])+1=6

dp[9]=max(dp[0],dp[1],dp[2],dp[5],dp[6],dp[7],dp[8])+1=7

 

가장 긴 증가하는 부분수열의 길이는 7이다

 

이 문제는 머리속으로는 이렇게 복잡하게 생각할 필요없는데 생각을 받아 적을라 하니 이렇게 복잡해진다...

 

 

 

이 논리를 코드로 구현하면

 

     for(int i=1;i<n;i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (list[j] < list[i] && dp[j] + 1 > dp[i])
                    dp[i] = dp[j] + 1;
            }
        }

 

이렇게 된다 

1. 먼저 자기자신으로 끝나는건 확실하니 길이를 1로 설정해준다 

 

2. 그리고 증가하는 수열(list[j]<list[i])일때 자기자신 이전까지의 수중에서 형성된 증가하는 부분 수열중에서 가장 긴 것의 길이+1=현재위치의 수로 끝나는 증가하는 부분 수열중에 가장 긴 것의 길이 이다

 

 

4. dp 배열에서 가장 큰 요소가 가장 긴 증가하는 부분 수열의 길이이다 

 

 

 

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]list=new int[n];
        int[]dp=new int[n];

        for(int i=0;i<n;i++){
            list[i]=sc.nextInt();
        }
        dp[0]=1;

        for(int i=1;i<n;i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (list[j] < list[i] && dp[j] + 1 > dp[i])
                    dp[i] = dp[j] + 1;
            }
        }

        int max=0;
        for(int i=0;i<n;i++){
            if(dp[i]>max)
                max=dp[i];
        }

        System.out.print(max);

    }
}