Q2631. 줄세우기

생각해보면 가장 긴 부분 수열 알고리즘 입니다.

줄세우는 방법은 오름차순이며,

오름차순으로 정렬된 아이들을 제외하곤 다른 아이들을 재정렬 해야 합니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2631 { static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.parseInt(st.nextToken()); dp = new int[2][num+1]; for (int i = 1; i <= num; i++) { st = new StringTokenizer(br.readLine()); dp[0][i] = Integer.parseInt(st.nextToken()); } for (int i = 1; i < num; i++) { int min = 0; int nowNum = dp[0][i]; for (int j = i+1; j <= num; j++) { if (nowNum < dp[0][j]) { if (min == 0 || min > dp[0][j]){ min = dp[0][j]; dp[1][j] = Math.max(dp[1][j], dp[1][i] + 1); } } } } int maxValue = 0; for (int i = 1; i <= num; i++) { maxValue = Math.max(maxValue, dp[1][i]); } maxValue += 1; System.out.println(num - maxValue); } }