[2565번] 전깃줄 JAVA☕

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

2565번: 전깃줄

알고리즘 [접근 방법]

먼저 문제에서는 서로 교차되지 않도록 하기 위해 철거되어야 할 전선의 최소 개수를 구하는 것이다.

 

하지만 그렇게 구하기에는 교차 여부를 확인해야 하기에 불편하다. 그렇다면 역으로 생각해보자. 철거되어야 할 전선의 최소 개수라 하면, 거꾸로 전체 전선의 개수에서 최대한 겹치지 않게 설치 가능한 개수를 구하여 빼면, 즉 (전체 전선 개수 - 설치 가능 개수) = 철거 개수 가된다.

 

한마디로 최대한 설치 가능한 개수를 구하면 된다는 뜻이다.

 

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

 

먼저 A와 B전봇대를 의미하는 2차원 배열과 메모이제이션 할 배열 두 가지가 필요하겠다. wire배열을 선언할 건데, wire[N][0] 이 A전봇대, wire[N][1] 이 B전봇대다. 또한 dp의 경우 방문 여부를 편하게 판단하기 위해 Integer 객체 배열로 선언했다. 

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

그리고 wire에 입력을 받았다는 가정하에, wire배열을 A전봇대 기준으로 정렬해야하된다. Arrays.sort() 메소드 자체에는 2차원 배열을 정렬해주는 것이 없으므로 comparator를 이용하여 다음과 같이 정렬한다.

int[][] wire = new int[N][2];
Integer[] dp = new Integer[N];
 
Arrays.sort(wire, Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		return o1[0] - o2[0];
	}
});

재귀로 풀려면 먼저 A전봇대의 탐색 기준값을 중심으로 B에 연결할 때 이전에 B에 연결된 전봇대 값보다 커야한다. 그래야 겹치지 않게 할 수 있지 않겠는가. 즉, N+1부터 마지막 까지 A전봇대를 기준으로 탐색하면서 B전봇대에 연결 가능 한지 여부를 확인하고, 연결 가능하다면 그 다음에 연결할 전선을 탐색하기 위해 재귀를 해주는 것이다. 

 

즉, 다음과 같이 구성할 수 있다.

static int recur(int N) {
		
	// 탐색하지 않았던 위치라면 
	if(dp[N] == null) {
			
		dp[N] = 1;	// 최솟값 1로 초기화 
			
		// A의 N번째와 이후의 전봇대들 비교 
		for(int i = N + 1; i < dp.length; i++) {
			
			/*
			 *  A전봇대의 N번째 전선이 연결되어있는 B전봇대보다 A의 i번째
			 *  전봇대의 전선이 이어진 B전봇대가 뒤에 있을 경우 
			 *  전선을 설치할 수 있음 
			 */
			if(wire[N][1] < wire[i][1]) {
				// 연결 가능한 전선의 경우의 수 중 큰 값을 dp에 저장한다.
				dp[N] = Math.max(dp[N], recur(i) + 1);
			}
		}
	}
	return dp[N];
}

ottom-Up 방식인 for문은 반대로 A전봇대를 기준으로 이전의 A전봇대들을 살펴보면서 메모이제이션을 하면 된다.

for(int i = 0; i < dp.length; i++) {
			
	dp[i] = 1;	// 최소 개수인 1로 초기화 
			
	/*
	 * i번째 전봇대를 기준으로 이전의 전봇대들의
	 * 전선을 연결하기 위한 탐색
	 * 즉, i번째 전봇대에 연결된 B전봇대는
	 * 탐색할 j번째 전봇대에 연결된 B전봇대보다 값이 커야함 
	 */
	for(int j = 0; j < i; j++) {
		if(wire[i][1] > wire[j][1]) {
			dp[i] = Math.max(dp[i], dp[j] + 1);
		}
	}
}

주석으로도 설명을 했지만, 위 처럼 i번째 A전봇대를 기준으로 그 이전의 전봇대들을 탐색하면서 이전의 A전봇대 중 B에 연결 가능하려면 i번째의 B전봇대보다 값이 작아야 한다.

만약 작다면 메모이제이션 된 값 + 1과 현재 i번째 메모이제이션 중 큰 값으로 갱신하는 것이다.

 

앞서 11053번 가장 긴 증가하는 부분 수열 문제의 알고리즘을 그대로 응용한 방법이 된다.

 

마지막으로 출력 값은 처음 말했듯 전체 전선 개수 - 설치 가능한 최대 개수를 빼주면 된다.

풀이 및 코드

- 방법 1 : [Scanner + Top-Down]

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
 
public class Main {
 
	static Integer[] dp;
	static int[][] wire;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		dp = new Integer[N];
		wire = new int[N][2];
		
		for(int i = 0; i < N; i++) {
			wire[i][0] = in.nextInt();
			wire[i][1] = in.nextInt();
		}
		
		// 첫 번째 원소(A전봇대)를 기준으로 오름차순으로 정
		Arrays.sort(wire, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		
 
		int max = 0;
		
		/*
		 *  i번째 A전봇를 기준으로 연결가능한 개수 탐색
		 *  및 최댓값 찾기
		 */
		 
		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;	// 최솟값 1로 초기화 
			
			// A의 N번째와 이후의 전봇대들 비교 
			for(int i = N + 1; i < dp.length; i++) {
				
				/*
				 *  A전봇대의 N번째 전선이 연결되어있는 B전봇대보다 A의 i번째
				 *  전봇대의 전선이 이어진 B전봇대가 뒤에 있을 경우 
				 *  전선을 설치할 수 있음 
				 */
				if(wire[N][1] < wire[i][1]) {
					// 연결 가능한 전선의 경우의 수 중 큰 값을 dp에 저장한다.
					dp[N] = Math.max(dp[N], recur(i) + 1);
				}
			}
		}
		return dp[N];
	}
	
}

- 방법 2 : [Scanner + Bottom-Up]

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] dp = new int[N];
		
		int[][] wire = new int[N][2];
        
		for(int i = 0; i < N; i++) {
 
			wire[i][0] = in.nextInt();
			wire[i][1] = in.nextInt();
		}
		
		// A전봇대를 기준으로 정렬 
		Arrays.sort(wire, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		
 
		for(int i = 0; i < dp.length; i++) {
			
			dp[i] = 1;	// 최소 개수인 1로 초기화 
			
			/*
			 * i번째 전봇대를 기준으로 이전의 전봇대들의
			 * 전선을 연결하기 위한 탐색
			 * 즉, i번째 전봇대에 연결된 B전봇대는
			 * 탐색할 j번째 전봇대에 연결된 B전봇대보다 값이 커야함 
			 */
			for(int j = 0; j < i; j++) {
				if(wire[i][1] > wire[j][1]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		
		int max = 0;
		for(int i = 0; i < N; i++) {
			max = Math.max(max, dp[i]);
		}
		
		// 전체 개수 - 설치 가능한 전깃줄 = 최소 철거 개수 
		System.out.println(N - max);
		
	}
 
}