문제
N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.
|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
입력
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.
예제 입력 1
6
20 1 15 8 4 10
예제 출력 1
62
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, ans;
static int[] arr = null;
static int[] temp = null;
static boolean[] check = null;
public static int calculate() {
int result = 0;
for(int i = 0; i < n - 1; i++) {
result += Math.abs(temp[i] - temp[i+1]);
}
return result;
}
public static void dfs(int deptNow, int dept) {
if(deptNow == dept) {
ans = Math.max(ans, calculate());
return;
}
for(int i = 0; i < n; i++) {
if(!check[i]) {
temp[deptNow] = arr[i];
check[i] = true;
dfs(deptNow + 1, dept);
check[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
temp = new int[n];
check = new boolean[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < n; i++) {
temp[0] = arr[i];
check[i] = true;
dfs(1, n);
check[i] = false;
}
System.out.println(ans);
}
}
백트래킹을 통해 모든 조합을 구한다.
N의 최대값이 8이고 8! (= 40320) 안에 해결 가능하므로 브루트포스 사용 가능.
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
[BOJ] 1697 - 숨바꼭질 JAVA (0) | 2021.02.11 |
---|---|
[BOJ] 10971 - 외판원 순회 2 JAVA (0) | 2021.02.11 |
[BOJ] 1107 - 리모컨 JAVA (0) | 2021.02.10 |
[BOJ] 1476 - 날짜 계산 JAVA (0) | 2021.02.10 |
[BOJ] 1744 - 수 묶기 JAVA (0) | 2021.02.10 |