[알고리즘 / 백준] 2565 - 전깃줄

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

문제는 위와 같으며, "가장 긴 증가하는 부분수열(LIS)" 과 유사한 방법으로 문제를 해결할 수 있습니다.

 

1. 먼저 전봇대 A의 위치를 기준으로 전깃줄 위치를 정렬합니다. (이후 현재 위치 이전까지 전깃줄과 겹치지 않는다는 것을 보장할 수 있음)

2. 전깃줄의 위치를 하나씩 이전 전깃줄들과 비교하면서 겹치는지 확인합니다.

3. 겹치지 않는 경우 "해당 위치까지 연결된 전깃줄의 수 + 1" 한 결과와 "현재 전깃줄의 위치까지 연결된 전깃줄의 수" 를 비교하여 더 큰 수를 현재 전깃줄의 위치까지 연결된 전깃줄의 수로 저장합니다.

4. 마지막 전깃줄까지 모두 확인한 뒤, 겹치지 않고 가장 많이 연결된 전깃줄의 수를 전체 전깃줄의 수에서 빼면 답을 구할 수 있습니다.

 

위 내용을 그림으로 살펴보면 다음과 같습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n = int(stdin.readline())
pos = []
for _ in range(n):
    a, b = map(int, stdin.readline().split())
    pos.append([a, b])
pos.sort()  # 전봇대 A 위치를 기준으로 오름차순 정렬하기

result = [1 for _ in range(n)]
for i in range(1, n):
    for j in range(i):
        if pos[i][1] > pos[j][1]:  # 이전 전깃줄과 곂치지 않는 경우
            result[i] = max(result[i], result[j] + 1)  # 이전 전깃줄까지 연결된 전깃줄 수 + 1 과 현재 전깃줄까지 연결된 전깃줄 수 중 더 큰 수 저장

print(n - max(result))  # 전체 전깃줄 수 - 겹치지 않게 가장 많은 전깃줄을 연결했을 때 전깃줄 수

 

자바 코드는 다음과 같습니다.

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

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

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

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

        int[] result = new int[n];
        Arrays.fill(result, 1);

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

        Arrays.sort(result);
        System.out.println(n - result[result.length - 1]);
    }
}