138. 2565(전깃줄)

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] Eline = new int[N][N];
		int[] DP = new int[N];

		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			Eline[i][0] = Integer.parseInt(tmp[0]);
			Eline[i][1] = Integer.parseInt(tmp[1]);
			DP[i] = 1;
		}

		Arrays.sort(Eline, (e1, e2) -> {
			return e1[0] - e2[0];
		});

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				if (Eline[i][1] > Eline[j][1]) {
					DP[i] = Math.max(DP[i], DP[j] + 1);
				}
			}
		}

		Arrays.sort(DP);

		System.out.println(N - DP[DP.length - 1]);
	}
}

문제요약

서로 교차되지 않게 할때 제거 할 전깃줄 최소 개수

설명

LIS (최장증가수열) 를 이용하면 된다.

 

LIS로 나온 최대의 수가 서로 교차되지 않는 최대의 수라고 생각하면된다.

 

따라서 총 전깃줄 - 서로 교차되지 않는 최대의 를 해주면 제거해야할 최소의 전깃줄 개수가 나오게 된다.

 

이 문제는 정확하게 파악을 못하겠다..

따라서 비슷한 유형이 나오면 LIS를 사용해야겠다는 소스만 얻어가자.