728x90
https://www.acmicpc.net/problem/2631
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 |