[백준 알고리즘] 2631번: 줄세우기 (JAVA)

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

2631번: 줄세우기

 

---

소스코드

package Baekjoon.DP;
import java.io.*;
import java.util.*;

class P2631 {
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];

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

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

        sb.append(N - Arrays.stream(dp).max().getAsInt());
        System.out.println(sb);
        
    }
}

 

 

---

풀이

★ 일반적인 LIS(Longest Increasing Subsequence, 최장 증가 수열)을 활용하는 문제입니다. 문제에서 주어진 수열을 가지고 예시를 들어보면, 3 7 5 2 6 1 4 이라는 값 중, 최장 증가 수열은 3, 5, 6인 것을 알 수 있습니다. 그럼 3, 5, 6은 고정되어 있고, 나머지 수인 7,2,1,4만 움직여서 주어진 수열을 오름차순 정렬할 수 있습니다. 

 

★ 최종적으로는 LIS 중 가장 긴 값을 찾아주고, 전체 값인 N에서 LIS를 빼준 값을 출력해주면 됩니다:)