[BOJ] 2568번 : 전깃줄 - 2

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

2568번: 전깃줄 - 2

 

 

분류 : LIS

 

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int[] lis;
    static Wire[] list;
    static Pair[] trace;
    static boolean[] visit;
    public static void main(String[] args) {

        Main Solve = new Main();
        int N = sc.nextInt();
        list = new Wire[N];
        lis = new int[N];
        visit = new boolean[500001];
        Vector<Integer> v = new Vector<>();
        trace = new Pair[100001];
        for(int i=0;i<100001;i++){
            trace[i] = new Pair();
        }
        for (int i = 0; i < N; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            list[i] = new Wire(s, e);
            visit[s] = true;
        }
        Arrays.sort(list);
        
        int pLis = 0, pArr =1;
        
        lis[pLis] = list[0].b;
        trace[0].first= 0;
        trace[0].second = list[0].a;
        
        while(pArr<N){
            
            if(lis[pLis] < list[pArr].b)
            {
                lis[++pLis] = list[pArr].b;
                trace[pArr].first = pLis;
                trace[pArr].second = list[pArr].a;
            }
            else
            {
                int ans = Solve.lower_bound(0,pLis,list[pArr].b);
                lis[ans-1] = list[pArr].b;
                
                trace[pArr].first = ans -1;
                trace[pArr].second = list[pArr].a;
            }
            pArr++;
        }
        
        out.println(N-(pLis+1));
        
        int len = 0;
        int p = pLis;
        Stack<Integer> st = new Stack<>();
        for(int i=N-1;i>=0;i--)
        {
            if(trace[i].first==p){
                st.push(trace[i].second);
                p--;
            }
        }
        while(!st.isEmpty()){
            visit[st.peek()] = false;
            st.pop();
        }
        
        for(int i=0;i<=500000;i++){
            if(visit[i])
                out.println(i);
        }
        out.flush();
    }

    int lower_bound(int start, int end, int target) {
        int mid;

        while (start < end) {
            mid = (start + end) / 2;
            if (lis[mid] < target)
                start = mid + 1;
            else
                end = mid;
        }
        return end + 1;
    }
}

class Wire implements Comparable<Wire> {
    int a;
    int b;

    Wire(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Wire o) {
        return this.a < o.a ? -1 : 1;
    }
}
class Pair{
    int first, second;

    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    public Pair() {
    }
}

LIS 문제 + LIS의 추적을 합친 문제이다.

처음에 다른 문제를 풀때 썼던 LIS 알고리즘을 복붙 해서 썼더니 틀리길래 새로 LIS 알고리즘을 구현해서 풀었다.

온라인 알고리즘 스터디를 같이 하고 있는 Crocus님의 도움을 받아 해결 완료