[BaekJoon] 2565번 전깃줄 (Java) 문제 풀이 [Gold 5]

문제

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

2565번: 전깃줄

 

어떻게 풀 것인가?

처음에는 아이디어가 떠오르지 않아서 많이 어려웠던 문제였다.

그래서 문제에 대한 힌트를 얻기위해서 

아래에 알고리즘 분류를 확인하였으나, 이게 무슨... DP문제였다.

문제가 너무 어려웠다...

 

3시간의 고민 끝에 다른 분의 풀이를 참고하여 문제를 풀 수 있었다.

참고 사항에 그분의 풀이를 업로드하였다.

 

교차 여부를 구현으로 한다면 너무나 어렵다. 그렇다면 여기서 역으로 생각해야했다. 철거되어야 할 전선의 최소 개수라 하면, 거꾸로 전체 전선의 개수에서 최대한 겹치지 않게 설치 가능한 개수를 구하여 빼면, 즉 (전체 전선 개수 - 설치 가능 개수) = 철거 개수 가 된다.

 

한마디로 최대한 설치 가능한 개수를 구하면 된다는 뜻이다. <- 여기까지 아이디어를 떠올린다면 아래부터는 정말 쉽다.

 

먼저 A전봇대 기준으로 i번째에 연결된 전깃줄을 잇고 이후 전선들을 탐색하면서 i번째가 연결된 B의 값보다 큰 경우들을 모두 탐색해보는 것이다. 결국 정렬된 A를 기준으로 B에 연결된 값들에서 LIS를 하면 된다는 것이다. 이전에 배웠던 LIS를 풀어봤다면 쉽게 접근할 수 있는 문제였다.

 

풀면서 놓쳤던점

아이디어 자체가 떠올리기가 힘들었다.

 

이 문제를 통해 얻어갈 것

LIS 문제에 대한 활용

 

내 코드 

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 Integer[] dp;
    static int[][] wire;

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

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

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

        StringTokenizer st;

        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;

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

        System.out.println(N - max);

    }

    static int recur(int N) {
        if (dp[N] == null) {
            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], recur(i) + 1);
                }
            }
        }
        return dp[N];
    }
}

 

참고

https://st-lab.tistory.com/138

[백준] 2565번 : 전깃줄 - JAVA [자바]