[BOJ]2352번 : 반도체 설계

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

2352번: 반도체 설계

 

 

분류 : 다이나믹 프로그래밍 , 그리디 알고리즘 , LIS

 

import java.io.*;
import java.util.*;

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static void main(String[] args) {

        int N = sc.nextInt();
        int[] list = new int[N];
        int[] lis = new int[N];
        
        for(int i=0;i<N;i++)
        {
            int e = sc.nextInt();
            list[i] = e;
        }
        
        lis[0] = list[0];
        int len = 1;
        for(int i=1;i<N;i++)
        {
            if(list[i]<lis[0]){
                lis[0] = list[i];
            }
            else if(list[i]>lis[len-1]){
                lis[len++] = list[i];
            }
            else{
                int index =Arrays.binarySearch(lis, 0,len,list[i]);
                index = index<0 ? -index-1 : index;
                lis[index]= list[i];
            }
        }
        out.println(len);
        out.flush();
    }
}
class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str += br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

 

N개의 포트와 반대쪽의 N개의 포트를 연결할 때 서로 꼬이지 않게 연결하는 해서 최대 몇 개 까지 연결할 수 있는지 구하는 문제이다.

전형적인 LIS 문제로써 N의 크기가 최대 40,000이므로 LCS (O(N^2)) 방법을 사용할 경우 시간 초과가 나게 되므로

(BinarySearch+dp) (O(N logN))를 사용하여 풀어야 한다.

 

내가 풀어온 LIS 문제 순서.

 

1. 1965번 : 상자 넣기      https://www.acmicpc.net/problem/1965

 

2. 2565번 : 전깃줄           https://www.acmicpc.net/problem/2565

 

3. 1365번 : 꼬인 전깃줄   https://www.acmicpc.net/problem/1365