[BOJ] 차이를 최대로

[10819] 차이를 최대로

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

10819번: 차이를 최대로

• N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.
• |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
• 순열을 사용해서 문제를 풀 때는 모든 순서를 구했을 때 N! 가지가 나오기 때문에
• 시간 복잡도를 고려서 N <= 10일때 순열을 사용하도록 한다.
• 시간 복잡도 = 다음순열 구하는 시간(N)  x 모든 순서(N!) = O(N*N!)

 

 

소스코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public void go() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		Arrays.sort(a);
		int max = Integer.MIN_VALUE;
		do {
			int sum = 0;
			for(int i = 0; i<n-1; i++) {
				sum+= Math.abs(a[i]-a[i+1]);
			}
			max = Math.max(max, sum);
		}while(next_permutation(a,n));
		System.out.println(max);
	}

	public boolean next_permutation(int[] a, int n) {
		int i = n - 1;
		while (i > 0 && a[i - 1] >= a[i]) {
			i -= 1;
		}
		if (i <= 0)
			return false;
		int j = n - 1;
		while (a[i - 1] >= a[j]) {
			j -= 1;
		}
		swap(a, i - 1, j);
		j = n - 1;
		while (i < j) {
			swap(a, i, j);
			i += 1;
			j -= 1;
		}
		return true;
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}