백준 2565 전깃줄 [JAVA]

문제 해석

• 문제의 예시대로 전봇대로 그리면 아래의 사진과 같다. (기준을 전봇대 A로 설정했기 때문에 활살표로 표현해봤다.
  

• 모든 단계를 작성하진 못했지만, 구하는 로직은 아래의 사진과 같다.
  

• 여기서 1 -> 1인 경우는 누락되는 것이 아닌가 생각할 수 있지만, 애초에 제거해야하는 전깃줄의 최솟값을 구하는 것이므로 전봇대A가 2인 경우에서 1->1인 전깃줄을 추가하지 않아도 이미 1에서 전깃줄 최댓값이 나오므로 결과적으로 바뀌는 것은 없을 것이다. (최소 제거 전깃줄 개수 = 총 전깃줄 개수 - 냅둬도 되는 전깃줄 개수 이므로!!!)

• 위와 같이 구했다면 아래와 같은 결과가 나올 것이다.

전봇대A가 1인 경우 정상적인 전깃줄의 개수 = 3
전봇대A가 2인 경우 정상적인 전깃줄의 개수 = 5
전봇대A가 3인 경우 정상적인 전깃줄의 개수 = 2
전봇대A가 4인 경우 정상적인 전깃줄의 개수  = 5
전봇대A가 5인 경우 정상적인 전깃줄의 개수  = 4
전봇대A가 6인 경우 정상적인 전깃줄의 개수 = 3
전봇대A가 7인 경우 정상적인 전깃줄의 개수 = 2
전봇대A가 8인 경우 정상적인 전깃줄의 개수 = 1

-> 없애야 하는 전깃줄의 최소 개수(=3) =  총 전깃줄 개수(=8) - 그대로 둬도 되는 경우의 전깃줄 최댓값(=5) 

값은 3이 나올 것이다.

코드

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

public class Main {

    static int[][] arr;
    static Integer[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

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

        arr = new int[N][2]; //A전봇대 - B전봇대
        dp = new Integer[N];

        for(int i = 0; i < N; i++){ //전깃줄 이어진 선 입력받기
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        //전봇대 정렬(왼쪽 A기준으로 정렬)
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        
        int max = Integer.MIN_VALUE;

        //전봇대 A를 순서대로 탐색 -> A를 기준으로 B 전봇대가 들어갈 수 있는지.
        for(int i = 0; i < N; i++) {
            max = Math.max(solution(i), max);
        }

        System.out.println(N - max);

        br.close();
    }

    //전봇대가 들어갈 수 있는지 없는 체크하는 메소드
    static int solution(int depth){
        if(dp[depth] == null) { //탐색하지 않은 경우
            dp[depth] = 1; //1로 초기화

            //A전봇대 기준으로 다음 전봇대와 비교한다.
            for (int i = depth + 1; i < dp.length; i++) {
                if (arr[depth][1] < arr[i][1]) { //전봇대B 연결된 부위가 커야 한다.
                    // 연결 가능한 전선의 경우의 수 중 큰 값을 dp에 저장
                    dp[depth] = Math.max(dp[depth], solution(i) + 1);
                }
            }
        }
        return dp[depth];
    }
}

결과

느낀 점

• 알고나면 진짜 쉬운 문제인데 왜 처음엔 그렇게 이해하기 어려웠는지 이해가 안간다... 😥 그래도 전보다 동적계획법에 대해 문제 이해하는 속도가 빨라진 것 같아서 뿌듯...🙆🏻‍♀️