99클럽 코테 스터디 31일차 TIL - 백준 2631 줄 세우기

Input

1. N(2~200): 아이들의 수
2. ~N. 번호

Output

1. 이동해야하는 최소 인원

Solve

DP, LIS

Code

import java.io.*;

public class BOJ_2631_줄세우기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

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

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

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