[PS] BOJ2352 반도체 설계 ( LIS ) with JAVA

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

2352번: 반도체 설계

 

◎ 문제풀이

 

 

 

선이 겹치지 않도록 회로를 구성할 때, 회로가 가질 수 있는 최대 선의 개수를 구하는 문제이다. 1 부터 4까지 선을 하나씩 추가하며 최적의 회로를 만들어 가면 된다. ( Greedy )

 

회로에 Start Point 순서대로 선을 하나씩 추가하려고 한다. '현재' 회로의 End Point 중 가장 큰 EndPoint가 추가하려는 선의 End Point보다 작으면 선을 바로 추가하면된다. 선이 서로 겹치지 않기 때문이다.

 

그러나

 

작다면 선이 겹침을 의미한다. 그러면 겹치게 만드는 선을 제거하면 된다. 

 

 

 

1번 선을 연결하고 2번 선을 연결하려고 한다. 1번 선의 엔드포인트가 2번 선의 엔드포인트보다 크다. 그럼 연결된 EndPoint 중에 가장 가까운 큰 값의 엔드포인트에 연결된 선을 제거한다. 

 

 

 

 1번 선을 제거한다.

 

 

 

3번선은 2번선보다 End Point가 크니 그대로 연결한다. 반면 4번 선은 3번 보다 EndPoint가 작다. 4번 선은 2번 엔드포인트와 연결되는데, 2번 엔드포인트와 가장 가까우면서 큰 엔드포인트는 3번이다. 3번 엔드포인트와 연결된 선을 제거한다. 

 

 

 

 

최종 완성된 회로의 모습이다. 연결하려는 엔드포인트와 가장 가까우면서 큰 엔드포인트를 탐색해야 하므로 이분탐색을 사용한다. ( 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;

//BOJ2352 반도체 설계
public class Main {

    static List<Integer> lines = new ArrayList<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        lines.add(Integer.parseInt(st.nextToken()));

        for(int i=1;i<n;i++){
            int value = Integer.parseInt(st.nextToken());
            if( value > lines.get(lines.size()-1)) lines.add(value); // 회로 엔드포인트 끝보다 큰 경우
            else {
                int index = binarySearch(0, lines.size()-1, value);  // 회로 엔드포인트 끝보다 작은 경우
                lines.set(index,value);
            }
        }

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

    public static int binarySearch(int start, int end, int value){
        if( start >= end ) return end; // 가장 가까우면서 큰 값 탐색 완료

        int mid = (start+end)/2;

        if (lines.get(mid) < value) return binarySearch(mid+1,end,value); //중간값보다 크면 중간값보다 더 큰 범위를 탐색
        else return binarySearch(start,mid,value); // 중간값보다 작으면 중간값을 최대로 한 가장 가까우면서 큰값을 탐색
    }
}