[백준] 10819: 차이를 최대로 - JAVA

20 Jun 2023 in Algorithm on 브루트포스 알고리즘

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

풀이

브루트포스, 백트래킹문제.

N정수가 주어지고 순서를 적절히 바꿔 다음 식의 최댓값을 구하는 문제였다.

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

배열을 저장하고 0 ~ N-1 까지의 인덱스를 순열로 만들어 계산 후 최댓값을 구해줬다.

이전 문제처럼 비트마스크를 이용해 방문처리했다.

---

메모리: 14944KB

시간: 148ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, ans;
    static int[] arr, selected;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        selected = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        ans = 0;
        makeOrder(0, 0);

        System.out.println(ans);
    }

    private static void makeOrder(int idx, int check) {
        if (idx == N) {
            ans = Math.max(caculate(), ans);
            return;
        }

        for (int i = 0; i < N; i++) {
            if ((check & (1 << i)) == 0) {
                selected[idx] = i;
                makeOrder(idx + 1, check + (1 << i));
            }
        }
    }

    private static int caculate() {
        int result = 0;
        for (int i = 1; i < N; i++) {
            result += Math.abs(arr[selected[i]] - arr[selected[i - 1]]);
        }
        return result;
    }

}