[Java] 백준 2631번 : 줄세우기 (feat: 최장 증가 부분 수열)

문제소개

 

해결과정

DP로 어떻게 해결할지 접근하며 처음에는 단순히 3차원 dp배열을 생성해

dp[아이를 옮긴 횟수][어떤 아이를 옮겼는지][몇 번째 인덱스로 옮겼는지] 와 같이 접근을 시도했지만 해결하지 못했다.

해결방법을 찾던 중 최장 증가 부분 수열을 이용해 문제를 푸는 것이라는 정보를 알게되었고, 최장 증가 부분 수열에 대해 공부했다.

 

최장 증가 부분 수열이란, 주어진 수열(혹은 배열)에서 임의의 원소를 쭉 뽑았을 때 항상 증가하는 순서로 원소를 뽑은 경우 중에서 가장 길이가 긴 수열을 의미한다.

 

예시로, {3, 4, 6, 1, 2, 4, 7, 9} 라는 수열이 존재할 때 {3, 4, 6, 7, 9} 혹은 {1, 2, 4, 7, 9}를 뽑는 것이 최장 증가 부분 수열을 구했다고 말할 수 있다.

 

이 문제에서 어떻게 최장 증가 부분 수열이 적용될 수 있을까?

학생들이 임의의 순서로 섞여있는 상황에서, 최장 증가 부분 수열의 크기를 구한다면 전체 N명 중에서 해당 수열의 크기를 뺀 나머지 인원들만 자리를 옮기는게 가장 이동을 적게할 수 있는 방법이 될 것이다!

 

이러한 최장 증가 부분 수열을 구하는 방법은 DP를 활용해 구할 수 있다.

다만, 입력값이 클 경우 이분 탐색을 활용해 구해야한다. DP를 활용해 구한다면 시간복잡도가 최대 O(n^2)이기 때문이다.

 

솔루션

package DP.백준2631번_줄세우기;

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

public class Main {

    static int N;
    static int[] dp;
    static int[] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        map = new int[N + 1];

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

        for (int i = 1; i < N + 1; i++) {
            int maxValue = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (map[i] > map[j] && dp[j] > maxValue) {
                    maxValue = dp[j];
                }
            }
            dp[i] = maxValue + 1;
        }
        int result = Arrays.stream(dp)
                .max()
                .orElse(0);

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