[백준]2565번 전깃줄2️⃣

2565번: 전깃줄

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);

    }
}