[백준] 2565 전깃줄 - DP + LIS JAVA

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

2565번: 전깃줄

코드설명

DP 의 LIS 문제입니다.

 

문제 로직입니다.

DP[N] 은 N번쨰 위치에서 최대의 전기줄 개수입니다.

우리가 궁극적으로 구하는것은 ( 전체 전깃줄 개수 - 최대 연결전깃줄(max) ) 로써, 없애야하는 전깃줄의 최소 개수입니다.

 

1. 먼저 전봇대 A의 오름차순 순서로 정렬합니다. 이떄 Arrays.sort 람다식을 활용합니다.

2. LIS를 구합니다. 이 문제에서 가장 긴 증가하는 부분 수열(LIS)을 구하는 이유는, 전깃줄이 겹치지 않으면서 가장 긴 전깃줄의 개수를 구하면 답을 구할 수 있기에 그렇습니다.

예시와 함께 설명해보겠습니다.

전봇대 A의 1번위치와 1번위치가 연결되었다고 가정합니다. DP[1] = 1 입니다. 전봇대 A의 1번 위치에서 1개의 전봇대가 최대입니다.

이제 전봇대 A의 2번위치와 7번 위치가 연결되었다고 가정합니다. DP[2] = 2 입니다. 전봇대 A[1] 보다 전봇대A[2]가 7로써 더 크기에 전깃줄이 겹치지 않습니다.

전봇대 A[3] 번위치가 3번과 연결되었다고 가정합니다. DP[2] = 2 입니다. 전봇대 A[2] 는 A[3]과 겹치기에 A[2]를 제거했다고 가정합니다. DP[3] = 2 라는 의미는 3번쨰 전봇대의 기준에서 달 수 있는 가장 많은 전봇대입니다.

 

마지막에는 처음에 언급했듯

없애야하는 전깃줄의 최소 개수 = (전체 전깃줄 개수) - (최대로 연결될 수 있는 전깃줄) 를 출력합니다.

코드

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

public class Main {
	
	public static int N, M;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	int[] dp = new int[N];
    	int[][] arr = new int[N][2];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i][0] = Integer.parseInt(st.nextToken());
    		arr[i][1] = Integer.parseInt(st.nextToken());
    	}
    	
    	Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]);
		
    	for(int i=0;i<N;i++) {
    		dp[i] = 1; //최소 개수인 1 로 초기화
    		for(int j=0;j<i;j++) {
    			if(arr[i][1] > arr[j][1]) {
    				dp[i] = Math.max(dp[i], dp[j] + 1);
    			}
    		}
    	}
    	
    	int max = 0;
    	for(int i=0; i<N;i++) {
    		max = Math.max(max,  dp[i]); //최대 전선개수
    	}
    	
    	System.out.println(N - max);
	}
}