[Day31]JAVA 백준 줄세우기(2631번)

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

 

---

🌘 문제 이해하기

• 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다.
•  이동 도중에 보니 아이들의 번호순서가 바뀌었다. 
• 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다.
• 위치를 옮기는 아이들의 수를 최소로 하려고 한다.
• N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

---

🌗 문제 자세히보기

 

7명의 아이들이 3 7 5 2 6 1 4 순서대로 줄을 서 있을 때 

7 ,  4 , 2 , 1 번 아이들을 옮기면 1 2 3 4 5 6 7 순서대로 배치 할 수 있다. 

 

3 7 5 2 6 1 4 중에 7 , 4 , 2 ,1 은 보면 현재 배열에서 최장 증가 부분 수열이 아닌 것들이다 

3 7 5 2 6 1 4  에서 증가하는 부분 수열 중 가낭 최장의 부분 수열은 3 5 6 이다.

 

즉 한 배열의 최장 증가 부분 수열을 길이를 구하고 모든 아이들의 수에서 수열 길이를 빼주면 옮겨야 하는 아이들의 최소 수가 나온다.

---

🌕 최종 코드

 

import java.io.*;
import java.util.*;
public class Main{

    public static void main(String[] args) throws IOException 
    {       
       Scanner sc = new Scanner(System.in);

       int num = Integer.parseInt(sc.nextLine()); //총아이들 수 
       
       int[] child = new int[num+1];
       int[] dp = new int[num+1];     

       for(int i=0;i<num;i++)
       {
            child[i] = Integer.parseInt(sc.nextLine()); 
            dp[i] = 1;         
       }

       int result = Integer.MIN_VALUE; //가장 큰 부분 수열의 길이    

       //최장 증가하는 부분 수열 구하기 
       for(int i=0;i<num;i++) //기준값
       {         
            for(int j=0;j<i;j++) //비교밧
            {
                //증가하는 부분 수열 
                if(child[i] > child[j])
                {
                    dp[i] = Math.max(dp[i],dp[j]+1);                  
                }
            }

           result = Math.max(result, dp[i]);
       }
       
       //최장 증가하는 부분 수열 외의 나머지 숫자들이 최종 변경해야하는 아이들 수
       System.out.println(num-result);

    }
}