[백준] 2565 전깃줄 - Dynamic Programming / Java

• 문제 링크

2565번: 전깃줄

 

• 풀이 과정

제거하여야 하는 전깃줄의 최소 개수가 아닌,

조건에 맞게 전깃줄을 최대로 설치할 수 있는 경우의 수를 구한 후 n 에서 빼는 방식으로 접근한다.

 

A 전봇대 기준(Pair.src) 으로 정렬한다. 그런 다음  LIS (최장 증가 부분 수열) 을 구하여 정답을 출력한다.

LIS 에 관한 문제는 아래에서 확인할 수 있다.

[백준] 11053 가장 긴 증가하는 부분 수열 - Dynamic Programming / Java

추가로 알게 된 점은 배열 정렬 시 람다식보다 Comparator 를 활용할 시 메모리와 성능 면에서 유리하였다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        Pair[] pairs = new Pair[n];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            pairs[i] = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(pairs, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.src - o2.src;
            }
        });

        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (pairs[i].dest > pairs[j].dest && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
            }

            max = Math.max(max, dp[i]);
        }

        bw.write(String.valueOf(n - max));
        bw.flush();
    }

    private static class Pair {
        int src, dest;

        public Pair(int src, int dest) {
            this.src = src;
            this.dest = dest;
        }
    }

}