[백준] 2631: 줄세우기 - JAVA

01 Sep 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

1번부터 N번까지 오름차순으로 줄을 세워야 하는데 위치를 옮기는 횟수를 최소로 해야한다.

즉, 현재 상태에서 가장 긴 증가하는 부분수열(LIS)를 찾고 거기에 포함되지 않는 것들만 옮기면 최소로 옮기는 것이 된다.

LIS는 다이나믹프로그래밍을 이용해 구할 수 있다.

0부터 N까지 탐색하는데, dp[i]의 값을 1로 해준다.

현재 위치(i)보다 이전의 원소(j)들 중에서 현재 원소보다 작은지 체크한다.(arr[i] > arr[j])

현재 원소 보다 작다면 dp[i]의 값과 비교하여 갱신한다.(dp[i] = Math.max(dp[i], dp[j] + 1))

---

메모리: 14072KB

시간: 132ms

언어: Java 11

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

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

}