BOJ 2565 전깃줄

 

2565번: 전깃줄

일단 LIS (가장 긴 증가하는 부분 수열) 의 응용문제이다. 따라서 LIS를 이용해서 풀면 쉽게 풀린다.

 

전깃줄이 이어져있는 전봇대 A-B 가 주어지면, 전봇대 A 의 위치대로 오름차순으로 정렬을 해준다.

이 때, 전깃줄이 서로 겹치지 않기 위해서는 전봇대 A가 소팅 되었을 때 1-1 2-2 3-3 ... N-N 이렇게 전봇대 B 역시 오름차순이어야 한다.

 

예시를 전봇대 A 로 소팅했을 때

1 - 8
2 - 2
3 - 9
4 - 1
6 - 4
7 - 6
9 - 7
10 - 10

이렇게 소팅이 되는데, 여기서 LIS 구조에 맞지 않는 것은 

1-8 / 3-9 / 4-1 이다. 따라서 이 세 전깃줄이 끊겨야 한다. 

 

위에서 알 수 있듯이, LIS 의 구조를 깨는 것이 바로 우리가 끊어줄 전깃줄의 최소 개수이다. 

따라서 전봇대 A를 소팅시키고나서, LIS 를 구한 후, 전체 전깃줄 개수에서 구해놓은 LIS 를 빼주면 된다.

 

아래는 전체 자바 소스이다. LIS 찾는 소스는 '가장 긴 증가하는 부분 수열'문제에서 사용한것과 동일하다.

또한 전봇대 A-B의 정보를 저장하기 위해서 fair 라는 클래스를 사용했다. 

class pair implements Comparable<pair>
{
	int left;
	int right;
	public int compareTo(pair o) {
		return left-o.left ;
	}
}

public class Main {
	static pair[]info = new pair[501];
	static int[] LIS;
	public static void main(String[] args)throws IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk= new StringTokenizer(br.readLine());
		int n = Integer.parseInt(stk.nextToken()); //전기줄 개수
		String[] s;
		int index, num;
		for(int i= 0 ; i< 501; i++) {
			info[i]=new pair();
			info[i].left=501;
		}
		LIS = new int[n];
		for(int i=0; i<n; i++) {
			s = br.readLine().split(" ");
			index = Integer.parseInt(s[0]);
			num = Integer.parseInt(s[1]);
			info[i].left=index;
			info[i].right=num;
		}
		Arrays.sort(info);

		for(int i =0 ; i<n; i++)  // LIS 찾기 
		{
			LIS[i]=1;
			int tmp = info[i].right;
			for(int j = 0; j<i ; j++) 
			{
				if(info[j].right<tmp && LIS[j]+1 > LIS[i]) LIS[i]=LIS[j]+1;
			}
		}
		Arrays.sort(LIS);
		int res = n - LIS[n-1]; //전깃줄 개수에서 LIS 개수 빼면 ,끊어여할 전깃줄의 개수가 나온다.
		System.out.println(res);
	}
}