[백준,BOJ 2565] 전깃줄(JAVA 구현)

 

-내 생각

  이 문제를 풀다가 약간 소름이 돋았다. 이전에 비슷한 문제를 풀었었던 것 같은데(블로그에 글은 올리지 않았다.) 그 당시에는 이러한 문제를 풀 때 2번부터 기준으로 할 때 1번이 가지는 값은 2번이 가지는 값보다 작은 경우만 카운트해서 풀었던 것 같은데, 그것이 LIS를 학습하고 나서 LIS인 줄 알 수 있었다.. 최대한 LIS로 풀어보기 위해 글을 검색해 보았는데 정확한 풀이법을 알 수 있었다.

 

-해법

  우선 A 또는 B 전봇대를 기준으로 오름차순 정렬을 수행한다. 이후 i번을 기준으로 i번 보다 작은 경우 값이 i번 보다 작게 가져야 한다. 즉 전깃줄을 제거하는 것이 아닌, 설치하는 개념으로 생각해보면, 2-2 일 때 1-8이므로 2 <8이 된다. 그렇다면 설치할 수 있는 수는 증가하지 않고 1로 고정이다. 다음 3의 경우 3-9일 때 2-2, 1-8 이므로 3번 또는 2, 3번 또는 1로 2개의 전깃줄을 설치할 수 있다. 이런 식으로 앞선 전깃줄이 자신보다 작은 값을 가질 경우만 카운트해주면, 최종적으로 LIS는 5개를 설치할 수 있다는 것을 알 수 있다. 그러나 문제가 요구하는 정답은 총전깃줄의 수에서 몇 개의 전깃줄을 제거하냐므로, 8-X =5 이므로 X =3이 된다. 

 

import java.util.*;

public class Main {
	static int n;
	
	static int dp[], cost[][];
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		dp = new int[n+1];
		cost = new int[n+1][2]; // A, B 전봇대 배열
		
		
		for(int i=1;i<=n;i++) {
			for(int j=0;j<2;j++) {
				cost[i][j] = sc.nextInt();
			}
		}
		
		Arrays.sort(cost,new Comparator<int[]>() { //A를 기준으로 오름차순 정렬

			@Override
			public int compare(int[] a, int[] b) {
				if(a[0]<b[0]) return -1;
				else if(a[0]>b[0]) return 1;
				return 0;
			}
			
		});
		
		dp[1] = 1;
		
		for(int i=2;i<=n;i++) { // LIS를 구하는 과정
			dp[i] =1;
			for(int j=1;j<i;j++) {
				if(cost[i][1]>cost[j][1]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
		}
		int max =Integer.MIN_VALUE; // 최댓값이 설치할 수 있는 전긴줄의 최대 개수
		for(int j=1;j<=n;j++) {
			if(dp[j]>max)
				max = dp[j];
		}
		
		System.out.println(n-max); // 최대 개수만큼 설치하면 동시에 최소 개수를 자르는 것이므로 N-MAX를 수행
		
		
	}
	
}