모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하시오.
LIS를 이용하는 문제이다.
알고리즘을 너무 오랜만에 풀기도 했고 LIS가 기억이 안나서 풀이를 전혀 생각못했는데 보고 적용하니 금방 이해는 되었다.
이 문제의 핵심은 선을 하나씩 더 그어가면서 안겹치게 가장 많이 그을 수 있느냐이다.
우선 line[N+1][2] 2차원 배열에 전봇대 A, B를 각각 저장한다.
이후 LIS를 위해서 A기준 오름차순으로 정렬한다.
이제 B를 기준으로 LIS를 구해준다.
다 구해진 dp에서 최대값을 찾아서 N에서 빼준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
class Main {
static int N;
static int[][] line;
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
line = new int[N + 1][2];
dp = new int[N + 1];
// 전깃줄 입력받기
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 2; j++) {
line[i][j] = Integer.parseInt(st.nextToken());
}
}
// A전봇대 오름차순 정렬
Arrays.sort(line, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
// LIS 수행
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (line[i][1] > line[j][1]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
// dp값 중에서 max 찾기
int max = Integer.MIN_VALUE;
for(int i = 1; i <= N; i++) {
max = Math.max(max, dp[i]);
}
System.out.println(N - max);
}
}