📖 [백준알고리즘 풀이] Q.10819 차이를 최대로 문제 풀이 - java

📖 문제

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

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서

다음 식의 최댓값을 구하는 프로그램을 작성하시오.

A[0] - A[1]

A[1] - A[2]

+ … +

A[N-2] - A[N-1]

🔍 접근법

Q.10819 차이를 최대로 문제입니다.

N개의 정수로 이루어진 배열 A가 주어졌을 때

이 배열에 들어있는 정수의 순서를 적절히 바꿔 다음 식의 최댓값을 구하는 문제입니다.

배열 A의 정수의 순서를 바꾼 모든 경우를 확인해 최댓값을 구할 수 있습니다.

brute force 방식으로 풀이가 가능하고

brute force로 모든 경우를 확인하기 위해

백트래킹을 사용해서 답을 구할 수 있습니다.

배열 A의 정수에 대해 모든 경우에 대해

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

식을 계산하며 최댓값을 구할 수 있습니다.

💻 코드

package problem.brute;

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

public class Main_10819 {

    static int n;
    static boolean[] visited;
    static int[] sequence,numbers;
    static int max = Integer.MIN_VALUE;

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


    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        sequence = new int[n+1];
        numbers = new int [n+1];
        visited = new boolean[n+1];
        String [] temp = br.readLine().split(" ");
        for(int i=1; i<=n; i++){
            numbers[i] = Integer.parseInt(temp[i-1]);
        }
    }

    public static void dfs(int depth) {
        if(depth==n+1){
            caculate();
            return;
        }
        for(int i=1; i<=n; i++){
            if(!visited[i]){
                visited[i] = true;
                sequence[depth] = numbers[i];
                dfs(depth+1);
                visited[i] = false;
            }
        }
    }

    public static void caculate(){
        int sum = 0;
        for(int i=1; i<=n-1; i++){
            sum+= Math.abs(sequence[i]-sequence[i+1]);
        }
        max = Math.max(max,sum);
    }
}

Written on March 5, 2021