99클럽 코테 스터디 31일차 TIL - 백준[2631]

문제 풀이

오늘의 문제 - 백준2631.줄세우기

나의 풀이

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();
    }
}