[백준] 2565 전깃줄

문제보기

자세히 보면 가긴증 문제임을 알 수 있따. 시작지점 기준으로 정렬 해주고, 도착지점만 뽑아서 수열을 만든다.

그리고 가장 긴 증가하는 부분수열 문제로 생각하고 풀면 된다~!

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

class Node{
  int start;
  int end;
  Node(int start, int end){
    this.start = start;
    this.end = end;
  }
}

public class Main{

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());

    List<Node> list = new ArrayList<>();

    for(int i = 0 ; i < n ; i++){
      StringTokenizer st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());
      list.add(new Node(start, end));
    }
		// 시작 지점 기준으로 정렬
    list.sort(new Comparator<Node>(){
      @Override
      public int compare(Node o1, Node o2){
        if(o1.start < o2.start){
          return -1;
        }else{
          return 1;
        }
      }
    }); 
    
    int[] ends = new int[n]; // 도착지점만 뽑아 수열로 만들것 
    int[] len = new int[n]; // i번째까지 가장 긴 증가수열 길이를 담을 배열
    for(int i = 0 ; i < n ; i++ ){
      ends[i] = list.get(i).end;
      len[i] = 1; // 1로 초기화
    }
		
    // 가긴증 코드 
    int max = 1;
    for(int i = 1; i < n ; i++ ){
      for(int j = 0 ; j < i ; j++ ){
        if(ends[j] < ends[i] && len[j] >= len[i]){
          len[i] = len[j] + 1;
          if(max < len[i]) max = len[i];
        }
      }
    }

    System.out.println(n-max); // 해당 수열을 제외한 나머지 전선은 끊어져야 한다

  }
}