문제
N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 값을 최대로 만들어야 한다.
|A[1] - A[2]| + |A[2] - A[3]| + ... + |A[N-1] - A[N]|
입력
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A를 이루고 있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.
예제
입력:
6
20 1 15 8 4 10출력:
62풀이
핵심 아이디어: N ≤ 8이므로 최대 8! = 40,320가지 순열을 모두 탐색한다. DFS + 방문 배열을 이용한 백트래킹으로 모든 순열을 생성하고, 각 순열에서 인접한 원소 차이의 절댓값 합을 계산하여 최댓값을 구한다.
- DFS 설계:
cnt는 현재까지 배치된 원소 수,bf는 이전 원소 값,sum은 현재까지의 합이다. - 재귀 탐색: 방문하지 않은 모든 원소를 순서대로 배치해보고, 마지막 원소(
cnt == n)까지 배치되면answer를 갱신한다. - 백트래킹: 원소를 배치하기 전
v[i] = true, 재귀 호출 후v[i] = false로 복원하여 다른 순열도 탐색한다. - 첫 번째 원소 처리:
cnt == 0일 때는 이전 원소가 없으므로 차이를 더하지 않는다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day304BOJ10819차이최대 {
static boolean[] v;
static int[] arr;
static int answer = 0;
static int n;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
arr = new int[n];
v = new boolean[n];
for (int i = 0; i < n; i++)
arr[i] = Integer.parseInt(st.nextToken());
dfs(0, 0, 0);
System.out.println(answer);
br.close();
}
static void dfs(int cnt, int bf, int sum) {
if (cnt == n) {
answer = Math.max(answer, sum);
return;
}
for (int i = 0; i < n; i++) {
if (v[i])
continue;
v[i] = true;
dfs(cnt + 1, arr[i], cnt == 0 ? 0 : sum + Math.abs(bf - arr[i]));
v[i] = false;
}
}
}복잡도
- 시간: O(N!) — N개의 원소로 만들 수 있는 모든 순열 탐색 (N ≤ 8이므로 최대 40,320)
- 공간: O(N) — 재귀 스택 깊이 N, 방문 배열 N