백준_10819 차이를 최대로(자바) / 브루드포스 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.back;

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

public class Back_10819 {
	static int n ;
    static int[] arr,temp;
    static int result;
    static boolean[] visited;
    public static void main(String[] args) throws NumberFormatException, IOException {
    	BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        n =  Integer.parseInt(br.readLine());
        arr =new int[n];
        visited =new boolean[n];
        temp =new int[n]; // 각순열 케이스를 담아줄 임시 저장소
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i <n ; i++) {
            arr[i] =Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
        
        perm(0);
        System.out.println(result);
    }
    private static void perm(int count){
        if(count == n){
            int sum =0;
            for (int i = 0; i <n-1 ; i++) {
                sum += Math.abs(temp[i] - temp[i+1]);
            }
            result = Math.max(result,sum);
            return;
        }
 
        for (int i = 0; i <n ; i++) {
            if(visited[i]){
                continue;
            }
            visited[i] =true;
            temp[count] = arr[i];
            perm(count+1);
            visited[i] =false;
        }
    }
}

- 이 문제는 브루드 포스 알고리즘 문제입니다.

 

- 여기서 활용할 방법은 순열입니다.

 

- 각각의 숫자에 대한 위치가 정해져야 풀 수 있기 때문에 순서가 필요합니다.

 

- 숫자의 구성 및 위치 지정이 끝나면 값의 차이의 절댓값을 결정해줍니다.