bj 2352 반도체 설계(LIS)

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

겹치는 회로를 없도록 하라.

-> 이전 회로에서 연결된 회로보다 아래에 있어야 한다.

-> 이전 회로보다 값이 커야 한다.

-> 이전 회로보다 값이 큰 순열의 사이즈를 구하라.

-> 최장 증가 부분 수열이다.

 

최장 증가 부분 수열의 길이를 구하는 방법은 현재 아는 지식으로는 2가지가 있다.

1. 이분 탐색

-> 리스트를 만든다.

-> 만약, 리스트의 마지막 요소보다 현재 인덱스의 값이 더 크다면 그냥 맨 뒤에 집어넣는다.(수열의 길이를 증가시킨다.)

-> 만약, 리스트의 마지막 요소보다 현재 인덱스의 값이 더 작다면 

-> 위치 인덱스를 구한다.

-> 위치 인덱스에 현재 인덱스의 값을 업데이트한다.

 

여기서, 이런 의문을 가졌다.

"업데이트 하면 수열이 깨지는 것이 아닌가?"

 

위의 방법의 근본은 수열의 길이를 구하는 것이다.

-> 완성된 리스트가 LIS는 아니다.

-> 완성된 리스트의 size는 맞다.

 

업데이트를 할 상황은 마지막 요소보다 현재 요소가 작을 때이다.

-> 즉, 업데이트를 하던 말던 리스트의 사이즈는 유지가 된다.

-> 하지만, 업데이트를 하지 않으면, 

-> 1,2,3,9,10 <- 6,7,8

-> 1,2,3,9,10 <- 7,8

-> 1,2,3,9,10 <- 8

-> `1,2,3,9,10 과 같이 더 길어질 수 있는 수열임에도 사이즈가 증가하지 않는 문제가 발생한다.

즉,

-> 1,2,3,9,10 <- 6,7,8 (size = 5)

-> 1,2,3,6,10 <- 7,8

-> 1,2,3,6,7 <- 8

-> 1,2,3,6,7,8 (size = 6)

과 같이 알맞은 LIS를 구할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[] lines;
    static List<Integer> lis;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stringTokenizer;
    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(bufferedReader.readLine());
        lines = new int[n];
        lis = new ArrayList<>();
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < n; i++) {
            lines[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        lis.add(lines[0]);
        for(int i = 1; i < n; i++){
            if(lis.get(lis.size()-1) < lines[i]){
                lis.add(lines[i]);
                continue;
            }
            int savingIndex = binarySearch(lines[i]);
            lis.remove(savingIndex);
            lis.add(savingIndex, lines[i]);
        }

        System.out.println(lis.size());
    }

    private static int binarySearch(int line) {
        int start = 0;
        int end = lis.size()-1;
        int result = 0;
        while(start <= end){
            int mid = (start + end) / 2;
            if(lis.get(mid) >= line){
                result = mid;
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return result;
    }
}

 

 

2. 이중 for문(dp)

6,2,5,1,7,4,8,3 의 수열이 있다하자.

이때, 이중 for문으로 자신 이하 인덱스의 자신 이하 값을 가진 길이의 가장 큰 값에 +1을 한 값을 추가함으로 최장 수열을 구하는 것이다.

 

-> 6,2,5,1,7,4,8,3

-> 1,0,0,0,0,0,0,0

 

-> 6,2,5,1,7,4,8,3

-> 1,1,0,0,0,0,0,0

 

-> 6,2,5,1,7,4,8,3

-> 1,1,2,0,0,0,0,0 ===> 5보다 2가 작고 1이 가장 큰 수열의 길이이니 1+1==2 를 추가해줬다.

 

-> 6,2,5,1,7,4,8,3

-> 1,1,2,1,0,0,0,0

 

-> 6,2,5,1,7,4,8,3

-> 1,1,2,1,3,0,0,0 ===> 7보다 5가 작고 2가 가장 큰 수열의 길이이니 3을 추가해줬다.

 

-> 6,2,5,1,7,4,8,3

-> 1,1,2,1,3,2,0,0 ===> 4보다 2가 작고 2의 수열의 길이는 1이니 2를 추가해줬다.

 

-> 6,2,5,1,7,4,8,3

-> 1,1,2,1,3,2,4,0 ===> 8보다 7이 작고 3이 가장 큰 수열의 길이이니 4를 추가해줬다.

 

-> 6,2,5,1,7,4,8,3

-> 1,1,2,1,3,2,4,2 ===> 위와 동일

 

즉, 가장 큰 수열의 길이는 4이다.

 

이 방법은 다만, 시간 복잡도가 복잡복잡하기 때문에 지양하는 것이 좋을 것 같다.