반응형
백트레킹을 이용하여 풀었습니다.
import java.util.*;
public class Main {
static int max = 0;
static int n;
static int[] arr;
static int[] newArr;
static boolean[] visited;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
arr = new int[n];
newArr = new int[n];
visited = new boolean[n];
for (int i=0; i<n; i++)
arr[i] = sc.nextInt();
bt(0);
System.out.print(max);
}
static void bt(int depth){
if (depth == n){
int sum = 0;
for (int i=0; i<n-1; i++)
sum += Math.abs(newArr[i+1]-newArr[i]);
max = Math.max(max, sum);
return;
}
for (int i=0; i<n; i++){
if (!visited[i]){
visited[i] = true;
newArr[depth] = arr[i];
bt(depth+1);
visited[i] = false;
}
}
}
}
반응형
'Algorithm' 카테고리의 다른 글
백준 10825번 국영수 [ Java ] (0) | 2021.01.03 |
---|---|
백준 10813번 공 바꾸기 [ Java ] (0) | 2021.01.03 |
백준 13913번 숨바꼭질4 [ Java ] (0) | 2021.01.03 |
백준 13549번 숨바꼭질 3 [ Java ] (0) | 2021.01.03 |
백준 6593번 상범 빌딩 [ Java ] (0) | 2021.01.02 |