[JAVA] BOJ(백준) - 전깃줄 - 2565

문제내용

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

2565번: 전깃줄

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

< 그림 1 >

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

---

문제 접근 방법

우선 첫번째로 접근했던 방법은 입력받은 전깃줄의 연결여부를 line[][] 배열에 저장해 놓고, 인덱스 차이로 계산하는 방법이였다.

예를 들어 line[1][8] 일때 line[2][2]를 본다면 인덱스차이는 2-1로 양수, 2-8로 음수가 나온다.

이렇게 한쪽은 양수, 한쪽은 음수인 경우는 전깃줄이 겹치는 경우이므로 이런 경우가 나왔을때 전깃줄을 제거해주는 방법으로 접근했다.

하지만 이런 접근 방법에는 어떤 전깃줄을 먼저 제거하냐의 문제와 dp배열에 저장해놓은 값을 활용해야하는데 이를 활용하지 못하는 문제점이 있고, 채점결과 틀린 코드로 됐다.

 

따라서 다른 방법을 찾아야했고 내가본 다른분들의 풀이방식은 전부

'제거 해야하는 최소 전깃줄 개수 = 전체 전깃줄개수 - 설치 가능한 최대 전깃줄 개수' 를 이용해 풀었다.

위의 풀이방식에선 설치 가능한 전깃줄의 개수를 필수로 구해야한다.

 

이때 입력받은 전깃줄의 개수를 'line[몇번째 전봇대인지][a,b전봇대] = a,b전봇대 위치번호' 배열로 정의하고,

'dp[전깃줄개수] = 설치가능한 최대 전깃줄개수' 배열을 정의했을때 풀이 방법은 아래와 같다.

 

1. A전봇대 기준으로 line배열을 오름차순 정렬한다. 정렬을 하는 이유는 A전봇대가 정렬됐을때 만약 B전봇대의 위치번호가 오름차순으로 이뤄진 LIS배열이 있다면 전깃줄을 연결할때 합선이 일어나지 않는다. 즉, 설치가능한 전깃줄이 된다.

B전봇대의 LIS배열은 {4 6 7 10}이 된다.

2. B전봇대의 LIS배열의 길이가 최대가 될때까지 dp에 값을 저장시킨다.

3. 입력받은 전깃줄 개수 - dp최댓값 이 정답이 된다.

 

1번의 의미를 말로 정리를 해보면 A전봇대에서 B전봇대로 전깃줄을 연결할 때 현재 인덱스값이 n이라면 n번째 B전봇대보다 n이전인 i번째 B전봇대값이 작아야한다. 한마디로 line[n][1] > line[i][1] 이 되야한다는 말이다.

 

그외에는 이전 LIS문제를 풀었을때와 같다.

 

풀이를 보고 생각해보자.

 

---

풀이

BottomUp

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

public class BOJ_2565_2 {
	static int[][] line;
	static Integer[] dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		int max = Integer.MIN_VALUE;
		line = new int[N][2];
		dp = new Integer[N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<line[0].length; j++) {
				line[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dp[0] = 1;
		
		//A전봇대 기준으로 정렬
		Arrays.sort(line, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]>o2[0]) return 1;
				else if(o1[0]<o2[0]) return -1;
				else return 0;
			}
		});
		
		for(int i=1; i<N; i++) {
			dp[i] = 1;
			for(int j=0; j<i; j++) {
				/*
				 * 현재(i)번째 B전봇대보다 이전(j)번째 B전봇대 값이 더 작아야 
				 * A전봇대와 연결했을때 합선이 일어나지 않고
				 * line[i][1]>line[j][1]조건에 만족하여 연결이 가능할때
				 * dp[i]가 dp[j]보다 작거나 같게되면 안됨. 왜냐면 이전값 보다
				 * 현재값에서 전깃줄을하나 더 연결할 수 있기때문임.
				 * 따라서 현재 dp[i]를 이전 dp값+1 을 해줌으로써 갱신시켜줌.
				 */
				if(line[i][1]>line[j][1] && dp[i]<=dp[j]) {
					dp[i] = dp[j]+1;
				}
			}
			max = Math.max(max, dp[i]);
		}
		
		System.out.println(N-max);
	}
}

 

TopDown

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

public class BOJ_2565_1 {
	static int[][] line;
	static Integer[] dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		int max = Integer.MIN_VALUE;
		line = new int[N][2];
		dp = new Integer[N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<line[0].length; j++) {
				line[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dp[0] = 1;
		
		Arrays.sort(line, new Comparator<int[]>() {
			
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]>o2[0]) return 1;
				else if(o1[0]<o2[0]) return -1;
				else return 0;
			}
		});
		
		for(int i=0; i<N; i++) {
			max = Math.max(max,LIS(i));
		}
		System.out.println(N-max);
	}

	public static int LIS(int n) {
		if(dp[n]==null) {
			dp[n] = 1;
			for(int i=n-1; i>=0; i--) {
				if(line[n][1]>line[i][1] && dp[n]<=LIS(i)) {
					dp[n] = dp[i]+1;
				}
			}
		}
		return dp[n];
	}
}

 

---

마치며

이번 문제는 풀이방법만 생각해내면 이전 LIS문제와 비슷하기 때문에 쉽게 풀수 있는 문제였지만

나는 생각해내지 못해서 너무 오래걸렸던 문제이다ㅠ.

 

참고로 Comaprator의 경우 모르겠다면 https://st-lab.tistory.com/243 이분 블로그에 잘 정리 돼있으니 공부해보는 것을 추천한다.