[백준] 2565번 : 전깃줄 - JAVA [자바]

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];
	}
});

(물론 람다식으로도 할 수 있지만, 문제는 필자가 찾아보니 람다식의 경우 바이트 코드로 변환하는 것이 아닌 언어 런타임에게 위임하기 때문에 시간와 메모리가 더 잡아먹는다고 한다.)

그러면 이제 탐색하는 메소드를 구성해야 한다. LIS를 풀어봤다면 금방 이해 될 것이다. 일단 크게 Top-Down 방식과 Bottom-Up 방식이 있는데, 먼저 Top-Down방식으로 재귀부터 보여주도록 하겠다.

 

재귀로 풀려면 먼저 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];
}

 

위의 방법이 대표적인 Top-Down방식이다. 위와같이 이후의 전봇대들의 연결 가능한 개수의 경우의 수 중 최댓값을 dp에 메모이제이션 해주면 된다.

 

 

 

 

Bottom-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번 가장 긴 증가하는 부분 수열 문제의 알고리즘을 그대로 응용한 방법이 된다.

 

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

 

 

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

Top-Down과 Bottom-Up 방식에 입력방법을 바꿔보면서 성능을 비교해보고자 한다.

 

 

1 . Scanner + Top-Down

2. BufferedReader + Top-Down

3 . Scanner + Bottom-Up

4. BufferedReader + Bottom-Up

 

 

 

 

---

• 풀이

- 방법 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];
	}
	
}

 

 

그리 어렵지 않았을 것이다. 아마 LIS를 풀어봤기 때문에 보더라도 금방 이해하셨으리라 본다. Top-Down방식이 좋은점은 역시 코드가 간결해진다는 장점..

 

 

---

- 방법 2 : [BufferedReader + Top-Down]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.  문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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

public class Main {

	static Integer[] dp;
	static int[][] wire;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		dp = new Integer[N];
		wire = new int[N][2];
		
		StringTokenizer st;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			wire[i][0] = Integer.parseInt(st.nextToken());
			wire[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 첫 번째 원소(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];
	}
	

}

 

 

 

성능은 말할 것도 없이 BufferedReader가 더 좋을 것이다.

 

 

 

 

 

---

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

 

 

 

반대로 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);
		
	}

}

 

 

 

가장 보편적인(?) 방법이지 않을까 싶다.

---

- 방법 4 : [BufferedReader + Bottom-Up]

 

 

 

어김없이 이번에도 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.  

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
        
		int[] dp = new int[N];	
		int[][] wire = new int[N][2];
		
		StringTokenizer st;
		for(int i = 0; i < wire.length; i++) {
			st = new StringTokenizer(br.readLine()," ");
			wire[i][0] = Integer.parseInt(st.nextToken());
			wire[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 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);
		
	}

}

 

 

 

성능은 말할 것도 없이 BufferedReader가 더 좋을 것이다.

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 22305019  -  방법 4 : BufferedReader + Bottom-Up

채점 번호 : 22305012  -  방법 3 : Scanner + Bottom-Up

채점 번호 : 22305007  -  방법 2 : BufferedReader + Top-Down

채점 번호 : 22305005  -  방법 1 : Scanner + Top-Down

 

 

 

---

• 정리

 

 

뭐.. 이번 문제는 LIS만 정확하게 풀 줄 알고 있다면 쉽게 풀었을 문제라.. 크게 설명할 것이 없었다. 문제 정답률도 높은편이기도 하고,,

 

문제는 앞으로 단계가 높아질 수록 설명해지기 난감해서 어떻게 해야할지가 매우 큰 고민이다. 어지간하면 그림으로 이해하기 쉽게 하려고 하는데, 필자가 포토샵은 잘 다루지 못해서(무엇보다 미적 감각이 떨어짐) 시간이 남는대로 조금씩 배워봐야겠다.

 

그리고 LIS, LDS 같은 유사 문제들이 백준에 꽤 있으니 한 번 이번 기회에 다른 문제들도 풀어보시는 걸 추천한다.

모르는 것 있거나 이해하기 어려운 것이 있다면 언제든 댓글 달아주시면 된다.