이번에 풀어본 문제는
백준 2565번 전깃줄 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Cable
{
    int start,end;

    public Cable(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
public class Main {
    static int N;
    static Cable [] cables;
    static int [] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        cables = new Cable[N];
        dp = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            cables[i] = new Cable(l,r);
        }

        //좌측값 기준으로 정렬
        Arrays.sort(cables, (c1, c2) -> c1.start - c2.start);

        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, solution(i));
        }

        System.out.print(N - max);
    }
    static int solution(int n) {
        if (dp[n] < 1) {
            dp[n] = 1;

            for (int i = n + 1; i < N; i++) {
                if (cables[n].end < cables[i].end) {
                    dp[n] = Math.max(dp[n], solution(i) + 1);
                }
            }
        }

        return dp[n];
    }
}

📝 풀이

입력된 N개의 전깃줄이 좌, 우측 전봇대를 잇고 있을 때, 모든 전깃줄이 서로 겹치지 않게 할 수 있는 최소한의 제거 횟수를 구하는 문제입니다.
문제에 주어진 대로 전깃줄을 제거하는 접근이 아닌, 조건에 맞게 전깃줄을 최대로 설치할 수 있는 경우의 수를 구해, N에서 빼주는 방식으로 풀어보았습니다.
먼저 입력된 배열을 좌측 전봇대 번호를 기준으로 정렬해 줍니다.
낮은 번호부터 탐색을 시작해, 뒷 번호에서 설치될 전깃줄이 조건에 맞게 설치될 수 있다면 재귀를 통해 해당 값에 1을 더한 값을 누적하여 더해질 수 있도록 하였습니다.
모든 번호의 탐색을 마치고, 최대 설치 개수를 N에서 빼주면 최소 제거횟수를 구할 수 있습니다.

📜 후기

dp인것 같았지만 도저히 풀 방법이 떠오르지 않아 다른 풀이를 참고하여 풀어봤습니다. 비슷한 유형의 문제가 있다고 하여, 해당 문제도 풀어볼 생각입니다.