[백준] 2631. 줄세우기

문제 링크

[백준] 2631. 줄세우기

풀이 과정

문제 예시를 보며 설명하겠습니다.

3, 5, 6번 학생들은 증가하는 순서대로 올바르게 줄을 섰으니, 나머지 7, 2, 1, 4번만 움직인다면, 그 횟수가 올바른 줄이 되기 위한 최소 횟수가 됩니다.

위와 같이 증가하는 순서대로 줄을 서야 하므로, LIS 알고리즘을 적용할 수 있습니다. 총 인원 N명에서 최장 증가 부분 수열의 길이를 뺀 값은 최소 변경 인원을 의미하므로, 그 값이 정답이 됩니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N];
        int[] dp = new int[N];
        int max = 0;

        for (int i = 0; i < N; i++) nums[i] = sc.nextInt();

        for (int i = 0; i < N; i++) {
            dp[i] = 1;

            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        for (int i = 0; i < N; i++) max = Math.max(max, dp[i]);
        
        System.out.println(N - max);
    }
}