Java

[백준 2631] 줄세우기 (JAVA)

iheeeee6-6 2023. 5. 23. 14:56
728x90

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

 

2631번: 줄세우기

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기

www.acmicpc.net

 

 

LIS 증가하는 수열의 최대 갯수를 찾아서

n -  LIS 하면 옮겨야 하는 최소값이 나온다 !

 

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		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 max=0;
		int[] dp = new int[n];
		dp[0]=1;
		for(int i=1;i<n;i++) {
			dp[i]=1;
			for(int j=0;j<i;j++) {
				if(arr[j]<arr[i]) {
					dp[i]=Math.max(dp[i],dp[j]+1);
				}
			}
			max= Math.max(max, dp[i]);
		}
		
		System.out.println(n-max);
		
	}

}

'Java' 카테고리의 다른 글

[백준 2573] 빙산 (JAVA)  (1) 2023.05.25
[백준 1937] 욕심쟁이 판다 (JAVA)  (0) 2023.05.23
[백준 2579] 계단 오르기 (JAVA)  (0) 2023.05.23
[백준 1915] 가장 큰 정사각형 (JAVA)  (0) 2023.05.22
[백준 11501] 주식 (JAVA)  (0) 2023.05.21