[백준(Baekjoon)][자바(java)] 2565 : 전깃줄 / 동적 계획법 1

 

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

2565번: 전깃줄

 

* 풀이 방법

예시의 경우,

A와 B가 연결된 각각의 위치는 다음과 같음

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

 

A에 연결된 위치들이 오름차순으로 정렬되어 있다는( LIS : 증가하는 수열일 때 ) 가정 하에,

B에 연결된 위치들 또한 오름차순으로 정렬되어야( LIS일 때 ) 전깃줄이 교차하지 않고 연결될 수 있음

즉, A를 기준으로 오름차순으로 정렬한 후, B에서 LIS를 구하고 그를 제외한 개수만큼 제거해야 함

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), i, j, max = 0;
		int a[][] = new int[n][2];
		int dp[] = new int[n];
		for( i = 0; i < n; i++ ) {
			a[i][0] = sc.nextInt();
			a[i][1] = sc.nextInt();
		}
        
		Arrays.sort( a, (o1, o2) -> {
			return Integer.compare( o1[0], o2[0] );
		});
        
		for( i = 0; i < n; i++ ) {
			dp[i] = 1;
			for( j = 0; j < i; j++ )
				if( a[j][1] < a[i][1] && dp[j] >= dp[i] )
					dp[i]++;
			max = max < dp[i] ? dp[i] : max;
		}
		
		System.out.println( n - max );
		sc.close();

	}
}