문제
두 전봇대 사이에 N개의 전깃줄이 연결되어 있다. 교차하지 않도록 하려면 최소 몇 개의 전깃줄을 제거해야 하는지 구하라.
입력
첫째 줄에 N (1 이상 100 이하), 이후 N개의 전깃줄 연결 정보 (A 위치, B 위치)가 주어진다.
출력
제거해야 하는 최소 전깃줄 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
8 1 8 3 9 2 2 4 1 6 4 10 10 9 7 7 6 | 3 |
풀이
A 기준 정렬 후, B에서의 최장 증가 부분 수열(LIS) 길이를 구한다. 제거 수 = N - LIS 길이.
- 전깃줄을 A 위치 기준으로 오름차순 정렬한다
- B 위치 배열에서 LIS를 O(N^2) DP로 구한다
dp[i]는 i번째까지의 LIS 길이이고, 이전 줄 j에서line[i][1] > line[j][1]이면 갱신한다- LIS 길이가 교차하지 않는 최대 전깃줄 수이므로,
N - LIS가 답이다
핵심 아이디어: 교차하지 않는 전깃줄 집합은 A, B 모두 증가하는 부분 수열이다. A 기준 정렬 후 B의 LIS를 구하면 된다.
코드
import java.io.*;
import java.util.*;
public class Day357BOJ2565전깃줄 {
static int N, ans = 0;
static int[][] line;
static Integer[] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
line = new int[N][];
dp = new Integer[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
line[i] = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
}
Arrays.sort(line, (o1, o2) -> o1[0] - o2[0]);
for (int i = 0; i < N; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (line[i][1] > line[j][1])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
ans = Math.max(ans, dp[i]);
}
System.out.println(N - ans);
br.close();
}
}복잡도
- 시간: O(N²)
- 공간: O(N)