2565번 문제

문제

풀이

구상

LIS를 한 번 공부하고 나면 쉽게 풀 수 있는 문제 같다.
바로 이전에 풀었던 반도체 설계와도 아주 유사하다.
다른 점이 있다면, 입력이 다르게 들어온다는 것이다.
A전봇대의 위치 번호가 큰 순대로 B전봇대에 연결되는 위치를 정렬한 뒤, LIS를 찾아야 한다.

• 나는 정렬을 위해 Collections.sort를 사용하였고, 이를 위해 Wire라는 static class를 만들어 ArrayList에 저장하였다.

이후 총 전깃줄의 개수 - LIS의 길이 를 구하면 답이 된다.

최종 제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int[] memo;
    static class Wire {
        int from;
        int to;
        public Wire(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Wire> wireList = new ArrayList<>();
        StringTokenizer st;
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            wireList.add(new Wire(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
        }
        
        Collections.sort(wireList, (o1,o2)-> {
            return o1.from - o2.from;
        });

        memo = new int[n+1];
        int len = 0;
        int idx = 0;
        for(int i=0; i<n; i++) {
            int cur = wireList.get(i).to;
            if(cur > memo[len]) {
                len++;
                memo[len] = cur;
            } else {
                idx = binarySearch(0, len, cur);
                memo[idx] = cur;
            }
        }

        System.out.println(n-len);
    }

    static int binarySearch(int left, int right, int key){
        int mid = 0;
        while(left < right) {
            mid = (left+right)/2;
            if(memo[mid] < key) {
                left = mid+1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

별다른 문제 없이 성공하였다.