BOJ_G5_2565

📁 [G5_2565] 전깃줄

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static int[] dp;
    static int[][] wire;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        dp = new int[N];
        wire = new int[N][N];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine()," ");
            wire[i][0] = Integer.parseInt(st.nextToken());
            wire[i][1] = Integer.parseInt(st.nextToken());
        }

        // 오름차순으로 정렬
        Arrays.sort(wire, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        // 풀이 방법
        // 연결할 수 있는 최대 전선 개수를 구해서 총 전선 개수에서 빼주면 최소 전선 삭제 수를 구할 수 있다.


        // 최댓값 ( 연결가능한 )
        int max = 0;

        // i번째 A전봇대를 개준으로 연결가능한 개수 탐색, 최댓값 찾기
        for(int i=0; i<N; i++){
            max = Math.max(max, recur(i));
        }

        // 전체 전선 개수 - 최댓값 = 최소로 없애는 전선 수
        System.out.println(N - max);

    }

    static int recur(int N) {
        // 처음 탐색하는 전봇대라면
        if(dp[N] == 0){

            // 최솟값을 1로 초기화
            dp[N] = 1;

            // A의 N번째와 이후의 전봇대들 비교
            for(int i=N+1; i<dp.length;i++){
                // 만약 연결할 수 있으면
                if(wire[N][1] < wire[i][1]){
                    // dp 배열에 더 큰 값을 저장해준다.
                    // A 전봇대의 N번째 전선이 연결되어있는 B전봇대보다
                    // A의 i번째 전봇대의 전선이 이어진 B전봇대가 뒤에있을 경우
                    // 전선을 설치할 수 있다.
                    dp[N] = Math.max(dp[N], recur(i) + 1);
                }
            }
        }
        return dp[N];
    }
}

🤔 나의 생각

반례를 다 넣었지만 통과해서 대체 뭐가 문젠지 알아보다 틀린 것을 깨달은 문제이다..
먼저 처음 생각한 방법은

1. 시작 좌표를 오름차순으로 정렬한다.
2. 각 좌표마다 겹치는 선의 개수를 구한다.
3. 최대 개수인 선을 삭제해 가며 전체 겹치는 선의 개수가 0일 때 까지 반복한다.
4. 반복하는 횟수를 카운팅해서 출력해준다.

이 방법에서 가장 큰 잘못은 최대로 겹치는 선이 여러개 나올때 무엇을 삭제하냐에 따라 최종 값이 달라진다는 점이다.
근데 .. 많은 질문 속의 반례를 해봤는데 나는 제대로 나와서.. 맞은 줄 알았는데 방법 자체가 틀린 것이였다..

그래서 찾아본 결과 방법은 dp를 사용하는 것이다..
약간 접근 방법이 다른 것이 삭제할 전선을 찾는 것이 아닌 최대로 연결할 수 있는 전선을 찾아 총 전선에서 빼는 것이다.
그래서 메모리제이션을 이용해 연결할 수 있는 최대 전선을 구해 총 전선에서 빼주면 된다.
역시.. dp는 처음에 접근을 못하면… 어렵다.. ㅎ