[BOJ] 2631. 줄 세우기 - Java

📝 문제

문제 | 백준 2631. 줄 세우기

💡 풀이 과정

⛓ 사용한 알고리즘 : LIS(최장 증가 부분 수열), DP

LIS(최장 증가 부분 수열)을 구하는 원리를 응용하면 쉽게 풀 수 있는 문제이다. LIS를 구현할 때는 DP와 이분탐색을 사용할 수 있는데, 이 문제에서는 N 의 최댓값이 200으로 크지 않기 때문에 DP를 사용해도 시간 복잡도가 크지 않아 DP로 풀이를 진행했다.

예를 들어, 다음과 같이 예제에서 LIS를 찾아보자.

[3, 7, 5, 2, 6, 1, 4]

위 배열에서 LIS는 [3, 5, 6] 이다. 따라서 이 세 숫자를 제외한 나머지 숫자를 적당한 위치로 옮겨주어야 오름차순 배열이 완성된다. 이 경우에는 N 이 7이므로 7-3=4 가 정답이 된다.

따라서 입력받은 배열에 대해 LIS를 구하고, LIS를 구성하는 원소의 개수를 N 에서 빼주면 정답을 쉽게 구할 수 있다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int[] arr = new int[N];
		int[] dp = new int[N];
		
		for(int i=0;i<N;i++) {
			arr[i] = sc.nextInt();
		} 
		
		int max = 0;
		for(int i=0;i<N;i++) {
			dp[i] = 1;
			for(int j=0;j<i;j++) {
				if(arr[j]<arr[i] && dp[j]+1>dp[i]) {
					dp[i] = dp[j]+1;
					max = Math.max(max, dp[i]);
				}
			}
		}
		
		System.out.println(N-max);
	}
}