[백준] 10819. 차이를 최대로

문제 링크

[백준] 10819. 차이를 최대로

풀이 과정

배열에 들어있는 수의 순서를 적절히 바꿔서 식의 최댓값을 구해야 하므로, 결국 모든 경우의 수를 다 구해보는 완전탐색 문제입니다.

for (int i = 0; i < N; i++) {
    used[i] = true;
    go(i, 0, 1);
    used[i] = false;
}

입력받은 배열을 순회하며, 식의 맨 처음에 사용할 A[0 으로 인덱스 i를 선택합니다. 이후 재귀 함수를 돌 때, 사용한 수라고 체크해두기 위해 used[i]를 true로 설정합니다. 이후 go()를 호출하며 내부적으로 최대값을 구하게 되고, 모든 호출 스택이 끝난 후 사용하지 않은 숫자라는 표시로 used[i]를 false로 설정해, 원상 복귀합니다.

static void go(int now, int sum, int cnt) {
    if (cnt == N) {
        answer = Math.max(answer, sum);

        return;
    }

    for (int next = 0; next < N; next++) {
        if (!used[next]) {
            used[next] = true;
            go(next, sum + Math.abs(values[now] - values[next]), cnt + 1);
            used[next] = false;
        }
    }
}

go()는 배열의 모든 수를 다른 순서로 사용해 식의 최대값을 계산합니다.

• now는 식의 내부 연산 중, |A[i]-A[j]|에 사용되는 인덱스 i를 가리킨다.
• sum은 현재까지의 누적합 값을 의미한다.
• cnt는 배열 내부에서 식 연산에 사용된 요소의 개수를 의미한다.

이후, 현재 부분 식 |A[i]-A[j]|에서의 j는 next로 설정해줍니다. 배열 내부 정수 중 사용하지 않은 값 next를 하나 선택한 후, 부분 식 계산을 한 값을 파라미터로 go()를 재귀 호출합니다.

코드

import java.util.Scanner;

public class Main {
    static int N;
    static int[] values;
    static boolean[] used;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        values = new int[N];
        used = new boolean[N];

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

        for (int i = 0; i < N; i++) {
            used[i] = true;
            go(i, 0, 1);
            used[i] = false;
        }

        System.out.println(answer);
    }

    static void go(int now, int sum, int cnt) {
        if (cnt == N) {
            answer = Math.max(answer, sum);

            return;
        }

        for (int next = 0; next < N; next++) {
            if (!used[next]) {
                used[next] = true;
                go(next, sum + Math.abs(values[now] - values[next]), cnt + 1);
                used[next] = false;
            }
        }
    }
}