2011.11.10 다시 풀어 봄
복습 할 때
이 문제는 놀랍게도 LIS와 연관지어 생각할 수가 있다.
사실 문제를 처음 보면 드는 생각은, a전봇대를 기준으로 모두 정렬해서, i 번째 전선의 b전봇대에서의 위치를 bx로 해서,
i보다 밑에 있는 전선들 중, b전봇대에서 bx보다 큰 값을 갖는 개수를 카운트하여, 겹치는 선을 가장 많이 가진 것을 제거시키는 식으로 생각이 들었다.
하지만 LIS로 생각하면 더 간단해진다.
- a전봇대를 기준으로 정렬한다.
- 생각해 보면, n-1번째 전선의 b(n-1)이 n번째 전선의 bn 보다 작다면, 두 전선은 겹칠일이 없다.
- 이말은 즉슨, bn이 increasing하는 일련의 전선들은 겹치지 않는 전선들이라는 것이다.
- 따라서 LIS로 생각하면 문제를 풀 수 있다.
- LIS 를 통해, 겹치지 않는 일련의 전선들의 최대 개수를 구하면, 제거하는 전선의 최소 개수를 구하는 것과 같아진다.
package coding;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main{
public static int n;
public static int[] cache = new int[501];
public static List<int[]> list = new ArrayList<>(101);
public static int max = 0;
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static void setting() throws IOException {
n = Integer.parseInt(br.readLine());
int t1=0,t2=0;
for(int i=0;i<n;i++){
st = new StringTokenizer(br.readLine());
t1 = Integer.parseInt(st.nextToken());
t2 = Integer.parseInt(st.nextToken());
list.add(new int[]{t1,t2});
}
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
}
public static void solve(){
int len = list.size(), curmax = 0;
for(int i=0;i<len;i++){
curmax = 0;
for(int j=0;j<i;j++){
// i 번째 전선 위쪽의 전선들 중, 현재 전선보다 b값이 더 낮은 전선 중, cache값이 가장 큰 것
if(list.get(j)[1]<list.get(i)[1]){
if(cache[j]>curmax)curmax = cache[j];
}
}
cache[i] = curmax+1;
max = Math.max(max,cache[i]);
}
}
public static void main(String[] args)throws IOException {
setting();
solve();
System.out.println((n-max));
}
}풀이생각
- 교차되는 경우
- (a,b)가 있을 때 1번 전봇대에서 1~a-1번까지의 위치들을 모두 확인 —> 그들이 2번 전봇대에 연결된 위치가 b+1번 이후이면, (a,b)와 교차하게 된다.
- 그리디하게는 풀면 안 될 것 같다.
- A 전봇대를 오름차순 정렬시켜야 될 것 같다.
다른 사람 풀이를 보았다.
생각하지 못한 부분
- 삭제 해야 하는 전깃줄의 최소개수로 생각하면 너무나 어렵다.
- 교차되지 않을 수 있는 전깃줄의 최대개수로 생각하여 , 이것을 전체 전깃줄의 수 - 최대개수를 하여, 제거해야할 전깃줄의 최소개수를 구할 수가 있다.
- 교차되지 않을 수 있는 전깃줄의 최대개수로 생각 —> 정렬 후 LIS.를 생각하게 될 수도 있었을 텐데..
풀이 01 : DP사용
-
오름차순 정렬까지는 생각나는데 그 뒤에는 전체탐색 따위 밖에 생각나지 않았다.
-
다른 사람 풀이를 보니, 전봇대 하나를 기준으로 오름차순 정렬을 한 후 LIS를 찾는 것으로 해야한다고 한다. 그렇다.. 예를들어 A를 기준으로 정렬하였을 때, B에 연결되어있는 번호가 오름차순이라면 교차되는 것이 없게 된다.
-
예를들어 밑의 예제의 경우 A를 기준으로 B 번호를 정렬시키면
8 2 9 1 4 6 7 10 -
여기서 LIS는 1,4,6,7,10
-
-
이렇게 나온 LIS를 전체 선의 개수에서 빼주면 —> 삭제시켜준 line의 개수가 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static class edge implements Comparable<edge>{
int v1; int v2;
public edge(){}
public edge(int av1,int av2){v1=av1;v2=av2;}
@Override
public int compareTo(edge o) {
return v1-o.v1;
}
}
public static int n; // the number of lines
public static List<edge> arr;
public static int[] cache;
public static int max=0;
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr= new ArrayList<>(n+1);
cache = new int[n+1];
Arrays.fill(cache,-1);
int v1=0,v2=0;
for(int i=0;i<n;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
edge e = new edge(v1,v2);
arr.add(e);
}
Collections.sort(arr);
}
public static void dp(){
// bottom up
for(int i=0;i<n;i++){
if(cache[i]==-1){
cache[i]=1;
for(int pre=i-1;pre>=0;pre--){
if(arr.get(pre).v2>=arr.get(i).v2)continue;
// 이전 index의 v2값이 더 작은 경우 ,
cache[i]=Math.max(cache[i],cache[pre]+1);
}
}
}
// max
for (int i : cache) {
if(i>max)max=i;
}
}
public static void main(String[] args) throws IOException {
Setting();
dp();
System.out.println(n-max);
}
}