[백준] 2565 전깃줄 - 자바

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

2565번: 전깃줄

문제 풀이

이 문제를 풀 때 접근법을 '어떤 전깃줄을 제거하느냐?'가 아니라 '어떤 전깃줄을 선택할 것인가?'로 두면 훨씬 쉽게 풀 수 있다.

선택하는 방법은 간단하다. 교차하지 않으려면 이전 A가 선택한 B의 전깃줄이 현재 선택하려는 B의 전깃줄보다 작으면 된다.

즉, A2가 B3을 골랐다면 A3은 B3보다 큰 전깃줄을 선택할 수 있게 된다.

 

선택 조건은 알았으니 답을 구하기 위해선 어떻게 해야 되는지 살펴보자.

먼저 maxConnection[]이라는 dp를 만들고 해당 값은 현재 index를 포함한 최대 연결 횟수를 말한다.

내가 A6 전깃줄을에 대한 maxConnection을 구하기 위해선 A6 이전 전깃줄에 대해 조건(A6의 B값이 더 커야한다는)이 성립하고, 그 중 제일 큰 값을 선택한면 된다.

 

코드

package 백준;

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

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

        int n = Integer.parseInt(br.readLine());
        int[][] wires = new int[n][2];
        int[] maxConnection = new int[n];

        for (int i = 0; i < n; i++) {
            wires[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(wires, (a, b) -> a[0] - b[0]);

        for (int i = 0; i < n; i++) {
            maxConnection[i] = 1;
            for (int j = 0; j < i; j++) {
                if (wires[i][1] > wires[j][1]) {
                    maxConnection[i] = Math.max(maxConnection[i], maxConnection[j] + 1);
                }
            }
        }

        System.out.println(n - Arrays.stream(maxConnection).max().getAsInt());
    }
}

느낀점

확실히 dp는 접근법과 규칙만 알아내면 쉽게 풀리는 것 같다. 하지만 이걸 알아내는 것이 제일 어렵다