백준 2631 줄세우기(LIS, DP)

2631번: 줄세우기

대표적인 LIS 문제이다.

 

처음 문제를 봤을 때 총 3가지로 생각 할 수 있었는데

 

1. 완전탐색 

모든 경우를 다 본다음에 그 중에서 가장 작은 녀석을 고르는 것

 

2. 그리디

오름차순으로 정렬하는 것이기 때문에 뒤에서 탐색해서 현재 값보다 큰 값을 만난다면 그 숫자를 이동시키는 로직 ==> 최소의 조건이 나오지 않음

 

3. LIS : 최장 부분 증가 수열

정렬을 최소로 하려고 하면 처음 주어진 배열에 대해서 증가를 보이는 애들은 그대로 놔두고 아닌 애들을 이동하는게 가장 최적일 것이다!

따라서, N - LIS를 구하는 것이 핵심

 

import java.lang.Math;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main_2631 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] data = new int[N];
        int[] dp = new int[N];

        for (int i = 0; i < N; i++) {
            data[i] = Integer.parseInt(br.readLine());
        }
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (data[i] > data[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        int max_value = 0;

        for (int i = 0; i < N; i++) {
            max_value = Math.max(max_value, dp[i]);
        }

        //System.out.println(Arrays.toString(dp));
        System.out.println(N - max_value);


    }
}