백준-10819번/차이를 최대로 (java)

 

문제 접근

 

이 문제는 | A[0]-A[1] | + | A[1]-A[2] | ................ | A[N-2]-A[N-1] | 의 최대 값을 구해줘야 한다.

따라서 모든 경우의 수에 대한 결과 값을 비교해 보면서 최대값을 찾는 브루트포스 알고리즘을 이용해야한다.

 

문제 풀이

 

 

dfs를 이용하여 배열의 순서에 대한 경우를 구해준다.

public static void dfs(int count){
    if(count==N){
        result = Math.max(result,getResult());
        return;
    }
    for(int i=0; i<N; i++){
        if(!visited[i]){
            visited[i]=true;
            selected[count]=arr[i];
            dfs(count+1);
            visited[i]=false;
        }
    }
}

 

count가 N이 됐다는 것은 바뀐 순서의 배열인  selected배열이 다 찼다는 것을 의미 하므로 selected 배열에 대한 결과값을 구해줘야 한다.

public static int getResult(){
    int sum = 0;
    for(int i=0; i<N-1; i++){
        sum+=Math.abs(selected[i]-selected[i+1]);
    }
    return sum;
}

**** Math.abs(x,y) ===> | x - y |의 절대값 ******

 

위의 getResult 메서드를 통해 | A[0]-A[1] | + | A[1]-A[2] | ................ | A[N-2]-A[N-1] | 를 구해주면

하나의 바뀐 경우에 대한 결과값을 구한 것이 된다.

이러한 과정을 dfs를 통해 계속 반복하면 결과값을 구할 수 있다.

 

<전체 코드>

import javax.imageio.IIOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Problem10819 {
    static int result=Integer.MIN_VALUE; //정수의 최솟값
    static int N;
    static int[] arr,selected;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);

        N=scanner.nextInt();
        arr=new int[N];
        visited = new boolean[N];
        selected = new int[N];

        for(int i=0; i<N; i++){
            arr[i]=scanner.nextInt();
        }

        dfs(0);
        System.out.println(result);
    }

    public static void dfs(int count){
        if(count==N){
            result = Math.max(result,getResult());
            return;
        }
        for(int i=0; i<N; i++){
            if(!visited[i]){
                visited[i]=true;
                selected[count]=arr[i];
                dfs(count+1);
                visited[i]=false;
            }
        }
    }
    public static int getResult(){
        int sum = 0;
        for(int i=0; i<N-1; i++){
            sum+=Math.abs(selected[i]-selected[i+1]);
        }
        return sum;
    }
}

 

 

느낀점 : 모든 경우에 대한 결과값을 비교할때는 dfs를 활용하자.