[백준/BOJ] 2631번: 줄세우기 - JAVA [자바]

---

2631번: 줄세우기

---

- 백준 2631번: 줄 세우기

• 문제

링크 참고

• 입력

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

• 출력

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

---

import java.util.Scanner;

public class BOJ_2631 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = Integer.parseInt(sc.nextLine());
		int[] students = new int[num];
		
		for(int i = 0 ; i < num ; i++) {
			students[i] = Integer.parseInt(sc.nextLine());
		}
		
		int[] dp = new int[num];
		dp[0] = 1;
		
		int ans = 0;
		
		for(int i = 1 ; i < num ; i++) {
			dp[i] = 1;
			
			for(int j = 0 ; j < i ; j++) {
				if(students[i] > students[j]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
			ans = Math.max(ans,  dp[i]);
		}
		System.out.println(num - ans);
		sc.close();
	}
}

---