본문 바로가기

PS

[BOJ]2352번 : 반도체 설계

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

 

2352번: 반도체 설계

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주

www.acmicpc.net

 

 

분류 : 다이나믹 프로그래밍 , 그리디 알고리즘 , 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 

'PS' 카테고리의 다른 글

[BOJ]5052번 : 전화번호 목록  (0) 2017.04.24
[BOJ]8983번 : 사냥꾼  (0) 2017.04.22
[BOJ]1890번 : 점프  (0) 2017.04.20
[BOJ]1620번: 나는야 포켓몬 마스터 이다솜  (0) 2017.04.19
[BOJ]1874번 : 스택 수열  (0) 2017.04.17