[LIS] 백준 2631 줄 세우기

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

2631번: 줄세우기

 

 

최장 증가 수열 (LIS, Longest Increasing Subsequence)

 

https://4legs-study.tistory.com/106

출처 : https://4legs-study.tistory.com/106

 

😢 수열의 한 원소에 대해, 그 원소에서 끝나는 최장 증가 수열을 생각해보자. 그 최장 증가 수열의 k를 제외한 모든 원소들은 반드시 k보다 작아야 할 것이다.

, 따라서 k의 앞 순서에 있는 모든 원소들 중 값이 k보다 작은 원소에 대해, 그 각각의 원소에서 끝나는 최장 증가 수열의 길이를 알고 있다면, k에서 끝나는 최장 증가 수열의 길이도 구할 수 있을 것이다.

 

 

 

 

 

 

🥸 부분 수열의 마지막 원소 K 보다 큰 내부 원소는 없어야 하며, k의 앞 순서 원소 각각의 최장 증가 수열의 길이를 알고있어야 한다. 

 

 

 

 

 만약 dp[j] + 1 와 같이 쓴다면, 이는 다음과 같은 의미이다.

 

     :: 이전 원소에서 끝나는 LIS에 현재 수를 붙인 새 (인덱스의)  LIS 길이 

 

따라서 dp[j] 가아닌 dp[j]+1 과 dp[i]를  비교해서 max 값을 만들어내는 것도 이러한 이유 때문이다.

 

 

 

 

 

public class LineUp_2631 {

    public static void main(String[] args) {
        // 3 7 5 2 6 1 4
        // 최소 방법으로 오름차순 배치 => 최소 수?
        // 3 5 6 의 최장 증가 수열을 제외한 아이들을 옮기는게 포인트
        int[] array = {3,7,5,2,6,1,4};

        int size = array.length;
        int[] dp = new int[size];
        for (int i = 0; i < array.length; i ++ ) {
            dp[i]=1;
            for (int j = 0; j< i; j ++) {
                if(array[j] < array[i] && dp[i] <= dp[j]) {
                    dp[i]++;
                }
            }
        }

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

        System.out.println(" ans : " + (size - max));

    }

}