import java.util.*;
public class Main {
public static boolean next_permutation(int a[]) {
int i = a.length - 1;
while(i > 0 && a[i - 1] >= a[i]) { // 1단계
i -= 1;
}
if(i <= 0) {
return false;
}
int j = a.length - 1;
while(a[j] <= a[i - 1]) { // 2단계
j -= 1;
}
int temp = a[i - 1]; // 3단계
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while(i < j) { // 4단계
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}
public static int calculate(int a[]) {
int sum = 0;
for(int i = 1; i < a.length; i++) {
sum += Math.abs(a[i] - a[i - 1]);
}
return sum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int answer = 0;
do {
answer = Math.max(answer, calculate(a));
} while(next_permutation(a));
System.out.println(answer);
}
}
배열을 정렬해주고 나서(첫순열인 오름차순을 구하기 위해), 순열을 모두 구하면서 그때마다 나오는 값 중에서 최대값을 구하면 된다.
import java.util.*;
public class Main {
public static boolean next_permutation(int a[]) {
int i = a.length - 1;
while(i > 0 && a[i - 1] >= a[i]) { // 1단계
i -= 1;
}
if(i <= 0) {
return false;
}
int j = a.length - 1;
while(a[j] <= a[i - 1]) { // 2단계
j -= 1;
}
int temp = a[i - 1]; // 3단계
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while(i < j) { // 4단계
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[][] = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
int d[] = new int[n];
for(int i = 0; i < n; i++) {
d[i] = i;
}
int answer = Integer.MAX_VALUE;
do {
if(d[0] != 0) {
break;
}
boolean ok = true;
int sum = 0;
for(int i = 0; i < n - 1; i++) {
if(a[d[i]][d[i + 1]] == 0) {
ok = false;
} else {
sum += a[d[i]][d[i + 1]];
}
}
if(ok && a[d[n - 1]][d[0]] != 0) {
sum += a[d[n - 1]][d[0]];
answer = Math.min(answer, sum);
}
} while(next_permutation(d));
System.out.println(answer);
}
}
N이 작기 때문에 순열로 풀 수 있다.
import java.util.*;
public class Main {
public static boolean next_permutation(int a[]) {
int i = a.length - 1;
while(i > 0 && a[i - 1] >= a[i]) { // 1단계
i -= 1;
}
if(i <= 0) {
return false;
}
int j = a.length - 1;
while(a[j] <= a[i - 1]) { // 2단계
j -= 1;
}
int temp = a[i - 1]; // 3단계
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while(i < j) { // 4단계
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
int n = sc.nextInt();
if(n == 0) {
break;
}
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int d[] = new int[n];
for(int i = 0; i < n; i++) {
if(i < n - 6) {
d[i] = 0;
} else {
d[i] = 1;
}
}
ArrayList<ArrayList<Integer>> answer = new ArrayList<>();
do {
ArrayList<Integer> cur = new ArrayList<>();
for(int i = 0; i < n; i++) {
if(d[i] == 1) {
cur.add(a[i]);
}
}
answer.add(cur);
} while(next_permutation(d));
Collections.sort(answer, new Comparator<ArrayList<Integer>>() {
public int compare(ArrayList<Integer> l1, ArrayList<Integer> l2) {
int n = l1.size();
int m = l2.size();
int i = 0;
while(i < n && i < m) {
int t1 = l1.get(i);
int t2 = l2.get(i);
if(t1 < t2) {
return -1;
} else if(t1 > t2) {
return 1;
}
i += 1;
}
if(i == n && i != m) {
return -1;
} else if(i != n && i == m) {
return 1;
}
return 0;
}
});
for(ArrayList<Integer> v : answer) {
for(int x : v) {
System.out.print(x + " ");
}
System.out.println();
}
System.out.println();
}
}
}
0을 k - 6개, 1을 6개 넣은 다음에 next_permutation을 수행하면 모든 조합을 구할 수 있다.