[백준] 2631 줄세우기 - DP + LIS JAVA

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

2631번: 줄세우기

코드설명

DP 문제 중에서 LIS 문제입니다.

 

LIS 는 Longest Increasing Subsequence 로써, 가장 증가하는 부분수열을 의미합니다.

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

입력
7
3
7
5
2
6
1
4

출력
4

주어진 입력
3 7 5 2 6 1 4

LIS DP 배열 값
1 2 2 1 3 1 2

3 5 6 일때 가장 증가하는 부분수열입니다.

이곳에서 7과 2 1 4 를 움직이게하면, 1 2 3 4 5 6 7 을 최소한의 숫자로 구할 수 있습니다.

 

코드

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

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[] arr;
	public static int[] dp;
	public static int max = 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());
    	arr = new int[N+1];
    	dp = new int[N+1];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken()); 
    	}
    	
    	for(int i=0;i<N;i++) {
    		dp[i] = 1;
    		for(int j=0;j < i; j++) {
    			if(arr[i] > arr[j]) {//만약 현재보다 크다면, 해당 dp값과 현재 dp값을 비교하여 더 큰값으로 갱신한다.
    				dp[i] = Math.max(dp[i],  dp[j] + 1);
    				max = Math.max(max,  dp[i]);
    			}
    		}
    	}
    	
    	System.out.println(N - max);
	}
}