[백준] 2565. 전깃줄

문제 링크

[백준] 2565. 전깃줄

풀이 과정

최장 증가 부분 수열 문제입니다.

주어진 전깃줄들을 순회하면서, 각 단계에서 이전까지 겹치지 않는 전깃줄들의 개수를 셀 수 있습니다.

문제에서 주어진 예시를 보며 아이디어를 알아보겠습니다. 위에서부터 전깃줄을 놓는다고 가정하면, 각 단계에서 겹치지 않고 설치할 수 있는 최대 전깃줄은 다음과 같습니다.

• 0번째 전깃줄(1-8)만 사용했을 때 : 1개 ( [1-8] )
• 1번째 전깃줄(2-2)까지 사용했을 때 : 1개 ( [2-2] )
• 2번째 전깃줄(3-9)까지 사용했을 때 : 2개 ( [2-2], [3-9] )
• 3번째 전깃줄(4-1)까지 사용했을 때 : 1개 ( [4-1] )
• 4번째 전깃줄(6-4)까지 사용했을 때 : 2개 ( [2-2], [6-4] )
• 5번째 전깃줄(7-6)까지 사용했을 때 : 3개 ( [2-2], [6-4], [7-6] )
• 6번째 전깃줄(9-7)까지 사용했을 때 : 4개 ( [2-2], [6-4], [7-6], [9-7] )
• 7번째(마지막) 전깃줄(10-10)까지 사용했을 때 : 5개 ( [2-2], [6-4], [7-6], [9-7], [10-10] )

즉, 마지막 전깃줄까지 사용했을 때 설치할 수 있는 최대 전깃줄들은 위와 같고, 없애야 하는 전깃줄의 개수는 3개임을 알 수 있습니다.

전깃줄이 겹치지 않기 위해서는 양 전봇대의 번호가 증가하는 순서로 이루어져야 합니다. 예를 들어, 전깃줄 [1-8]과 전깃줄 [2-2]는 겹치지만, 전깃줄 [1-8]과 전깃줄 [3-9]는 겹치지 않습니다.

즉, 전깃줄을 순회하되, 이전 전깃줄의 시작 번호보다 현재 전깃줄의 시작 번호가 크고, 동시에 이전 전깃줄의 끝 번호보다 현재 전깃줄의 끝 번호가 커야 현재 보고 있는 전깃줄을 추가로 설치할 수 있게 됩니다.

위의 규칙이 최장 증가 부분 수열을 구하는 알고리즘과 일치하므로, 아래와 같은 코드로 해결할 수 있습니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Pair[] pairs = new Pair[N];
        int[] dp = new int[N];
        int cnt = 0;

        for (int i = 0; i < N; i++) pairs[i] = new Pair(sc.nextInt(), sc.nextInt());

        Arrays.sort(pairs, (o1, o2) -> o1.start - o2.start);

        for (int i = 0; i < N; i++) {
            dp[i] = 1;

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

        for (int i = 0; i < N; i++) cnt = Math.max(cnt, dp[i]);

        System.out.println(N - cnt);
    }

    static class Pair {
        int start, end;

        public Pair(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}