[백준 2631번] 줄세우기- java

문제 설명

1. N개의 학생이 있다.

2. 학생들을 키순서대로 세워야 한다.

3. 키순서로 세우기 위해 이동시켜야 하는 학생의 최소 숫자를 구하면 된다.

 

풀이 과정

 1. DP를 통해서 진행한다.  '가장 긴 증가하는 부분 수열' 문제의 알고리즘을 적용해야 한다. 이전 문제를 풀어봤으면 사실 그 하위호환 문제이다. 근데왜 같은 골5...?

 2. 옮길 학생이 아니라, 움직이지 않을 학생수를 구하자! 예를 들어 여기 문제처럼

3 7 5 2 6 1 4

를 보면

가장 긴 증가하는 부분 수열로 구하면 3 - 5 - 6 이렇게 학생들을 보면 얘네가 가장 긴 증가하는 부분 수열이고, 움직이지 않을 최대 숫자이다.

 3. 그럼 이제 나머지 애들을 움직여주면 된다.

코드