백준 2565번: 전깃줄

문제

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

2565번: 전깃줄

---

풀이

두 전봇대 a와 b 사이에 설치된 전깃줄 중에 몇 개의 전깃줄을 없애 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제로 LIS(Longest Increasing Subsequence)를 응용하여 해결했습니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

poleA 배열은 전봇대 a에 설치된 전깃줄의 위치를 의미하며 arr 배열은 임의의 수 x가 있을 때 전봇대 a의 x번 위치에 설치된 전깃줄이 연결된 전봇대 b의 위치(arr[x])를의미합니다.

또한 dp[poleA[x]]는 전봇대 a의 poleA[0]번부터 poleA[x]번까지 모든 전깃줄이 교차하지 않는 전깃줄의 최대 개수를 의미합니다. 즉 11053번 문제에서의 dp 배열은 각 인덱스가 맨 오른쪽인 부분 수열이 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 의미하는 것과 유사합니다.

LIS 함수에서 dp[poleA[idx]]가 0이라면 1로 초기화한 뒤에 i를 포함한 for문에서 arr[poleA[idx]]와 arr[poleA[idx보다 앞쪽에 있는 인덱스(i)]]를 비교합니다. 만약 arr[poleA[i]]가 arr[poleA[idx]]보다 작다면 LIS 함수를 재귀적으로 실행하며 dp[poleA[idx]] 값을 최신화한 후에 for문이 끝나면 그 값을 반환합니다.

모든 입력이 끝나면 poleA 배열을 오름차순으로 정렬해준 다음에 i를 포함한 for문에서 LIS(i)를 1부터 n까지 실행하며 최댓값 max를 구하는데 이는 모든 전깃줄이 서로 교차하지 않는 최대 개수를 의미하므로 n - max를 출력하여 없애야 하는 전깃줄의 최소 개수를 구합니다.

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

public class Main {

    static int[] poleA, arr, dp;

    public static int LIS(int idx) {
        if (dp[poleA[idx]] == 0) {
            dp[poleA[idx]] = 1;
            for (int i = idx - 1; i >= 0; i--) {
                if (arr[poleA[idx]] > arr[poleA[i]]) {
                    dp[poleA[idx]] = Math.max(dp[poleA[idx]], LIS(i) + 1);
                }
            }
        }
        return dp[poleA[idx]];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        poleA = new int[n];
        dp = new int[501];
        arr = new int[501];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            poleA[i] = Integer.parseInt(st.nextToken());
            arr[poleA[i]] = Integer.parseInt(st.nextToken());
        }
        int max = 0;
        Arrays.sort(poleA);
        for (int i = 0; i < n; i++) {
            max = Math.max(LIS(i), max);
        }
        System.out.println(n - max);
    }
}

C언어

바텀업 방식을 이용한 코드입니다.

dp 배열을 비롯한 arr 배열, poleA 배열은 탑다운 방식의 코드에서의 의미와 동일하며 i를 포함한 for문으로 poleA[i]값과 arr[poleA[i]] 값을 입력받으며 dp[poleA[i]]는 1로 초기화합니다.

이후 poleA 배열을 오름차순으로 정렬해준 다음에 i와 j를 포함한 이중 for문으로 arr[poleA[i]]값이 arr[poleA[i보다 앞에 있는 인덱스(j)]]보다 크고 dp[poleA[i]]보다 dp[poleA[j]] + 1이 크다면 그 값을 넣어줍니다.

이후 i를 포함한 for문에서 dp[poleA[i]] 값을 비교하며 최댓값 max를 구하는데 이는 위의 코드와 마찬가지로 모든 전깃줄이 서로 교차하지 않는 최대 개수를 의미하므로 n - max를 출력하여 없애야 하는 전깃줄의 최소 개수를 구합니다.

#include <stdio.h>
#include <stdlib.h>
#define math_max(a, b) a > b ? a : b
int arr[501], dp[501];
int compare(const void* a, const void* b) {
	int o1 = *(int*)a;
	int o2 = *(int*)b;
	if (o1 > o2) return 1;
	else if (o1 < o2) return -1;
	else return 0;
}
main() {
	int n;
	scanf("%d", &n);
	int* poleA = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &poleA[i]);
		scanf("%d", &arr[poleA[i]]);
		dp[poleA[i]] = 1;
	}
	qsort(poleA, n, sizeof(int), compare);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[poleA[i]] > arr[poleA[j]] && dp[poleA[i]] < dp[poleA[j]] + 1) {
				dp[poleA[i]] = dp[poleA[j]] + 1;
			}
		}
	}
	int max = 0;
	for (int i = 0; i < n; i++) {
		max = math_max(max, dp[poleA[i]]);
	}
	printf("%d", n - max);
}

 

---

결론

LIS를 응용하여 문제를 해결하였습니다. 처음에 이 문제를 풀 때 poleA 배열을 만들지 않고 전봇대 a에 설치되지 않은 위치까지 모두 검사했는데 다시 보니 비효율적이라고 느껴졌지만 위치 번호의 범위가 작아서 속도 차이가 크게 나지는 않았습니다.