백준 7570 - 줄세우기 ( Java )

 

안녕하세요 besforyou 입니다

 

---

문제 풀이

 

어린이들이 줄 서있을때 어린이들의 최소한의 이동으로 줄 정렬을 시킬 수 있는 경우의 이동 횟수를 구하고 싶은것이 문제이다.

 

이 문제를 쉽게 풀기 위해서는 최소한의 이동 방법을 찾는것이 아니라, 전체 어린이 수에서 연속된 배열의 길이를 빼면 되는 문제이다.

 

 

예로 어린이들이 아래와 같이 줄을 섰다고 가정해보자.

 

2

5

6

1

3

4

 

여기서 가장 긴 연속된 배열은

 

2

5

6

1

3

4

 

2 , 3, 4 이다.

 

즉 2, 3, 4는 그대로 놔두고 5, 6, 1의 자리만 바꾸어주면 되는것이다. 따라서 정답은 전체 어린이 수 - 가장 긴 연속된 배열이다.

 

가장 긴 연속된 배열은 dp 로 구한다.

 

---

코드

 

import java.util.Scanner;
 
public class Main {
    public static void main (String [] args) {
 
        Scanner sc = new Scanner(System.in);
 
        final int MAX = 1000001;
        int n , max = -1;
        int dp[] = new int[MAX];
 
        n = sc.nextInt();
 
        for ( int i = 1 ; i <= n ; i++ ) {
            int j = sc.nextInt();
            dp[j] = dp[j-1] + 1;
            if ( max < dp[j] ) max = dp[j];
        }
 
        System.out.print( n - max );
 
    }
}