[백준][Java] 2631 - 줄세우기

1. 문제 정보

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

2631번: 줄세우기

난이도 : G4

유형 : DP, LIS

시간 : O(N^2)

---

2. 문제 풀이

주어진 줄에서 가장 긴 증가하는 부분 수열을 찾아내면 된다.
가장 길게 증가하는 부분 수열을 제외한 나머지 원소들만 자리를 바꿔야 최소 값이 나오기 때문이다.

 

3 7 5 2 6 1 4

예시에서 주어진 줄을 보면

3 x 5 x 6 x x  부분 수열이 가장 길게 증가하는 수열이다.
이 부분 수열은 괜히 자리를 변경을 해줄 필요가 없다.
어차피 이 부분 수열을 자기들끼리 오름차 순으로 증가한 상태이기 때문이다. 

가장 긴 부분 수열을 구하는 방법은 
LIS 알고리즘을 이용하면 된다.

LIS 알고리즘 로직은 N^2인 로직과,  NlogN 로직이 있다.
문제의 입력 크기가 작으니 전자의 로직으로 해도 상관없다.

 

---

3. 코드

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

public class Main {

    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final StringBuilder sb = new StringBuilder();

    int N;
    int[] numbers;
    int[] dp;
    int max;

    private void solution() throws IOException {

        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }

        max = 0;
        dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (numbers[j] < numbers[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        System.out.println(N - max);
    }

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        main.solution();
    }
}