백준 2631 줄세우기

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

2631번: 줄세우기

 

자기 전에 간단한 문제를 풀어보았습니다. 애들을 줄 세우는데 최소 몇 번 옮겨서 줄을 다시 맞출 수 있는지를 구하는 문제로, LIS 와 동일합니다. 

 

학생들이 3 7 5 2 6 1 4 로 줄을 서 있다면 맨 앞에 학생부터 자기가 최대 몇 번 째 증가 수열의 원소가 될 수 있는지 구하면 됩니다.

 

3 => 1

7 => 2

5 => 2

2 => 1

6 => 3

1 => 1

4 => 2

 

이므로 6번 학생이 마지막 번호인 경우가 최대 증가 수열이고, 나머지 4명의 학생을 따로 불러서 번호에 맞게 들어가라고 하면 됩니다.

 

자기 전이라 조금 코드가 비효율적이지만 N<=200 이므로 널널하게 돌아갑니다.

 

코드는 다음과 같습니다.