[자바] 백준 10819번: 차이를 최대로

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

10819번: 차이를 최대로

숫자 개수가 많지 않기 때문에

모든 경우를 계산해도 시간이 충분하다.

 

순열 알고리즘을 이용해서 n개의 숫자를 줄세우는 모든 경우의 수를 구하고,

각각의 경우의 결과값을 계산한 후, 최댓값을 출력한다.

 

-(참고)순열을 출력하는 perm함수

n개의 숫자를 줄세우는 모든 경우를 계산한다.

	static void swap(int[] arr,int i, int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	static void perm(int[] arr, int i, int n) {
		if(i==n) {
			for(int k=0;k<=n;k++) {
				System.out.print(arr[k]+" ");
			}
			System.out.println();
		}
		else {
			for(int j=i;j<=n;j++) {
				swap(arr,i,j);
				perm(arr,i+1,n);
				swap(arr,i,j);
			}
		}
	}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P10819 {
	static int result=0;
	public static void main(String[] args) throws IOException {

		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n= Integer.parseInt(br.readLine());
		int[] arr=new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		perm(arr,0,n-1);
		System.out.println(result);
	}
	static void swap(int[] arr,int i, int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	static void perm(int[] arr, int i, int n) {
		if(i==n) {
			result=Math.max(result, calc_sum(arr));
		}
		else {
			for(int j=i;j<=n;j++) {
				swap(arr,i,j);
				perm(arr,i+1,n);
				swap(arr,i,j);
			}
		}
	}
	static int calc_sum(int[] list) {
		int sum=0;
		for(int i=0;i<list.length-1;i++) {
			
			sum+=Math.abs(list[i]-list[i+1]);
		}
		return sum;
	}

}