정올 Q1871 줄세우기

정올 Q1871 줄세우기

▶ 문제 http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1144&sca=3050

3 7 5 2 6 1 4

주어진 숫자를 최소한으로 이동하여 정렬하는 방법을 구하는 문제이다.

위 문제의 경우 7, 4, 1, 2를 옴겨 4번만에 정렬된 숫자열을 구할 수 있다.

▶ 문제 접근

 정렬알고리즘을 사용하여 문제를 푸는 것으로 접근하였다. 선택과 삽입중 고민하여 교환 횟수를 카운트하는 방법을 시도하였다. 여기에 다이나믹을 접목하여 f(n)의 n은 숫자으 갯수로 생각하여 문제에 접근하였다. 

하지만 f(n)들간의 관계를 정리하기 힘들었고 정렬의 특성상 최소한의 방법을 구하기 보다 각숫자를 삽입 교환하는 것 이하로 줄어들지 못하였다.

▶ 문제 풀이

 다이나믹을 활용하면 의외로 쉽게 풀리는 문제이다.

 이 문제의 정렬되기전 주어진 순열에서 최대의 길이로 정렬된 순자의 열을 찾는 것이다. 

위 문제에서는 3, 5, 6 으로 정렬된 최대길이의 순자열이다. 이 숫자열 이외의 4개의 수를 이동하면 최소 이동 횟수를 구할 수 있다.

 이를 구하는 방법은 가장 높은탑 쌓기와 유사한 방법으로 구할 수 있다. 

가장 뒤에서 부터(위 문제의 숫자 4) 자기를 포함하여 오른쪽에 자기보다 큰 숫자중 최대길이를 가진 숫자를 찾는 것이다.

f(n)을 구해보자

f(6) = 1

f(6)(6번째 위치한 4를 뜻한다.)는 4보다 오른쪽에 위치한 숫자는 없으므로 자기 자신의 길이인 1이다.

f(5) = 2

오른쪽에 4가 있으며 1,4는 정상 순열이기에 1+f(6)이므로 2이다.

f(4) = 1, f(3) = 2, f(2) = 2, f(1) = 1, f(0) = 3이다. 

올바른 최대 길이의 순열은 3이므로 답은 7-3=4 가된다.

package Dinamic;
 
import java.util.Scanner;
 
 
public class Q1871 {
    static int[] input;
    static int[] maxVal;
    static int[] result;
    static int count;
    public static void main(String[] args) {
        //입력부
        Scanner sc = new Scanner(System.in);
        count = sc.nextInt();
        input = new int[count];
        for(int i =0;i<count;i++){
            input[i] = sc.nextInt();
        }
        maxVal = new int[count];
        result = new int[count];
        
        //실행함수
        dinamic();
        
        //출력부
        int min=Integer.MAX_VALUE;
        for(int i =0;i<count;i++){
            result[i] = count-maxVal[i];
            if(min>result[i]){
                min = result[i];
            }
        }
        System.out.println(min);
    }
    public static void dinamic(){
        for(int i = count-1;i>=0;i--){
            int max = 0; 
            for(int j =i+1;j<count;j++){
                if(input[i]<input[j]){
                    if(max<maxVal[j]){
                        max = maxVal[j];
                    }
                }
            }
            maxVal[i] = max+1;
        }
    }
    
 
}