백준 2565 전깃줄

백준 2565 전깃줄

백준 2565 전깃줄

구현 전 생각

전깃줄 1번 부터 출발한다
A전봇대에서 B전봇대로 뻗어가는 전깃줄의 값을 이후에나올 A 전깃줄의 값과 비교하여 A보다 작은 곳을 향하는 곳이 있을경우 겹침이 발생한다. 그 겹침이 한개라도 발생 한다면 해당 전깃줄을 삭제 빼는 방법으로 전체 전깃줄에서 겹치는 전기줄을 삭제한다. 단 이때 어떤 가장 겹치는 카운트 수가 많은 전기줄을 제거한다.

---

아쉬운점

해당 방법으로 큰수에서 작은 수를 갈때를 세지 못해서 전체적인 최적해를 찾지 못하였습니다.
-> LIS방식이용

코드

package com.study39;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class backjoon_2565_전깃줄 {
	static int map[][];
	static class line implements Comparable<line>{
		int a,b;

		public line(int a, int b) {
			super();
			this.a = a;
			this.b = b;
		}

		@Override
		public int compareTo(line o) {
			// TODO Auto-generated method stub
			return this.a-o.a;
		}
		
		
	}
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int N = sc.nextInt();
		
		line[] arr =new line[N];//data
		int[] LIS = new int[N];
		
		for (int i = 0; i < N; i++) {
			int a =sc.nextInt();
			int b =sc.nextInt();
			arr[i]=new line(a,b);
			
		}
		
		Arrays.sort(arr);
		Arrays.fill(LIS, 1);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i].b>arr[j].b)
				LIS[i]=Math.max(LIS[i], LIS[j]+1);
			}
		}
		Arrays.sort(LIS);
		System.out.println(N-LIS[N-1]);
		
	}
}