[백준] 2565 전깃줄 / 자바(Java)

문제

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

2565번: 전깃줄

 

---

해설

어느 전기줄들을 제거해야 교차되는 전기줄이 없을까 확인하는 문제입니다.

 

풀이방식을 어떻게 잡을지 몰라 고민했지만 DP를 사용해 해결하였습니다.

 

DP배열의 의미는

dp[i] => i번째 까지에서 교차되지 않으려면 설치하는 최소 전기줄 수

로 하였습니다. 제거가 아닌 설치를 기준으로 생각해서 좀 더 문제를 해석하기 쉽도록 되었습니다.

 

같은 위치에는 2개이상의 전기줄이 연결될 수 없으므로 입력 값을 정렬해주면 시작점기준으로 차례대로 값을 확인할 수 있습니다. 시작점이 더 클 때 끝점이 더 크면 해당 전기줄은 절대로 교차되지 않는다는 것을 통해 dp에서 한 값씩 구할 수 있었습니다.

 

---

코드

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 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] dp = new int[line];
        int[][] wire = new int[line][2];

        StringTokenizer st;

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

        Arrays.sort(wire, Comparator.comparingInt(o -> o[0]));

        int max = 0;
        for (int i = 0; i < line; i++) {
            max = Math.max(rec(wire,dp,i),max);
        }

        System.out.println(line-max);


    }

    static int rec(int[][] wire, int[] dp, int N){
        // 처음 탐색하는 경우
        if(dp[N]==0){
            dp[N]=1;
            //현단계 이후의 와이어들과 비교
            for (int i = N+1; i < dp.length; i++) {
                // 설치 가능한 경우
                if(wire[N][1]<wire[i][1]){
                    dp[N] = Math.max(dp[N],rec(wire,dp,i)+1);

                }
            }
        }
        return dp[N];
    }
}