링크

차이를 최대로

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

풀이

이번 문제는 백트레킹 문제로서 완전 탐색을 통해 문제를 풀었다.
완전탐색을 구하기전 시간 복잡도를 계산하였을 때 주어지는 숫자는 3<input<8 이기에 N-1*N!로 완전탐색을 하여도 1초라는 시간안에 문제를 풀수있을거라 판단하여 쉽게 완전탐색을 통해 문제를 풀었다.

코드

package com.company.BackTracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class MinusMax {
    static int[] arr,temp;
    static int N;
    static int max=Integer.MIN_VALUE;
    static boolean[] visit;
    static void input() throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        arr=new int[N];
        temp=new int[N];
        visit=new boolean[N];
        StringTokenizer st=new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
    }
    static void pro(int depth){
        if(depth==N){
            int sum=0;
            for(int i=0;i<N-1;i++){
                sum+=Math.abs(temp[i+1]-temp[i]);
            }
            max=Math.max(max,sum);
            return;
        }
        else{
            for(int i=0;i<N;i++){
                if(!visit[i]){
                    visit[i]=true;
                    temp[depth]=arr[i];
                    pro(depth+1);
                    visit[i]=false;
                }
            }
        }

    }
    public static void main(String[] args) throws IOException {
        input();
        pro(0);
        System.out.println(max);
    }
}

아쉬웠던점

이 문제 같은 경우 1초와 주어지는 N이 작기에 완전탐색을 통해 풀수있어 배열에 하나하나씩 다 때려넣으면서 풀어도 풀릴 수 있었다. 하지만 이러한 조건이 아닌 N이 더 커진다면 어떠한 방법으로 풀어야할까..