[BOJ] 백준 2565 - 전깃줄 풀이

1. 문제

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

2. Error Point

• 없애야 하는 전깃줄 수를 구하기 위해 입력받은 전깃줄을 탐색하면서 하나라도 교차하면 카운트하는식으로 생각함 → 이 후 어찌 처리해야 하는지 감이 안옴
• 없애야 하는 전깃줄의 최소 개수를 구하기 위해 반대로 생각하여 전체 전깃줄 수 - 교차하지 않는 최대 전깃줄 수 = 없애야 하는 전깃줄의 최소 개수.
• 즉 교차하지 않는 최대 전깃줄 수를 구하고 전체 전깃줄 수에서 빼주면 없애야 하는 전깃줄의 최소 개수가 나온다.
  
  
  

3. 풀이 Point

• <그림1>에서 위치가 순서대로 정렬되있는 것을 보고 정렬을 생각해냄
• 주어진 전깃줄의 A 위치 값을 오름차순으로 정렬
• 그 후 2개의 pointer를 잡고 반복문을 Start

1. 기준점을 잡는 pointer (이하 i라고 한다.)
2. 0번째부터 기준점 전까지 탐색하는 pointer (이하 j라고 한다.)

• i번째 전깃줄을 탐색할 때 이 전깃줄은 교차하지 않고 최대로 놓을 수 있는 전깃줄 수에 포함시키고, j번째 전깃줄을 탐색하면서 A는 정렬되었고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수는 없다고 문제에서 주어졌으므로, i의 B 값이 j의 B 값보다 크다면 이는 연결될 수 있는 전깃줄이다.
• 탐색을 완료 후 i가 어디에서 최대가 나오는지 확인해야하므로, Arrays를 오름차순으로 정렬 후 마지막 인덱스를 찾으면 답. → 탐색할 때마다 최대를 갱신한다면 정렬를 안해도 될 듯
  
  
  

4. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static class Line {
        int A;
        int B;

        public Line(int a, int b) {
            A = a;
            B = b;
        }
    }

    static List<Line> lineList = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            lineList.add(new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        Collections.sort(lineList, new Comparator<Line>() {
            @Override
            public int compare(Line o1, Line o2) {
                return o1.A - o2.A;
            }
        });

        int[] dp = new int[T];

        for (int i = 0; i < T; i++) {
            Line line_i = lineList.get(i);
						// i번째 전깃줄은 포함한다고 생각
            dp[i] = 1;

            for (int j = 0; j < i; j++) {
                Line line_j = lineList.get(j);

                if (line_j.B < line_i.B) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        Arrays.sort(dp);
        bw.write(Integer.toString(T - dp[T - 1]));

        bw.flush();
        bw.close();
        br.close();
    }
}

5. 점수

75/100