[백준] 2565번 : 전깃줄 Java

문제

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

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

 

<그림 1>

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

 

입력

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

 

출력

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

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

2565번: 전깃줄

접근

여기서는 설치할 수 있는 최대값을 구한 뒤, 이를 전체 전선 개수에서 제외하여

잘라야하는 전선의 개수를 구해줄 것이다.

 

먼저 A 전봇대를 기준으로 번호가 작은 순으로 정렬을 한다.(같은 위치에 두 개 이상의 전깃줄이 연결되지 않았음으로 B에 대한 정렬은 생략한다.)

 

간단히 정리를 위해B(i) = A의 i번째 전선이 연결된 B 전봇대의 위치라고 칭하겠다.

 

i번째 전선을 자르지 않는다면

1) i 이전의 전선은 B(i)보다 작아야 한다.

2) i 이후의 전선은 B(i)보다 커야 한다. 

 

완전 탐색을 하면 간단하게 풀리겠지만,

애석하게도 이 경우 n^2만큼 계산해야 하며 시간초과가 된다.

 

메모라이제이션과 dp를 사용한다면

 

i 번째 전선의 경우,

0~i-1 까지의 전선 중 1)의 조건을 이용하여 설치할 수 있는 전선의 최대값을 구하고

여기에 i번째 전선 1개를 추가하여 최대값을 구하여 기록한다.

 

이를 n번째까지 반복하며,

가장 많은 전선을 설치한 수를 구하여

이를 n에서 제외한 값을 출력한다.

 

구현

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 Main {
	//https://www.acmicpc.net/problem/2565
	public static int solution(int[][] lines) {
		//dp를 기록할 배열 선언
		int[] dp = new int[lines.length];
		//A전봇대 위치 기준으로 정렬, 같은 위치에 두개 이상 전깃줄 없음
		Arrays.sort(lines, (x,y)->(x[0]-y[0]));
		//설치 개수
		int answer = 0;
		for(int i=0;i<lines.length;i++) {
			//이전 전선들의 최대값과 비교
			for(int j=0;j<i;j++) {
				//B 전봇대에 자신보다 작은 순서일 경우 설치 가능
				if(lines[i][1]>lines[j][1]) {
					//이들 중 최대값을 취함
					dp[i]=Math.max(dp[i], dp[j]);
				}
			}
			//본인 자신의 전선 수(+1)
			dp[i]++;
			//최대값을 답으로 취함
			answer = Math.max(answer, dp[i]);
		}
		//(전체 - 설치개수) 출력
		return lines.length-answer;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] lines = new int[t][2];
		for(int i=0;i<t;i++) {
			st=new StringTokenizer(br.readLine());
			lines[i][0]=Integer.parseInt(st.nextToken()); //A전봇대 위치
			lines[i][1]=Integer.parseInt(st.nextToken()); //B전봇대 위치
		}
		System.out.println(solution(lines));
		br.close();
	}
}