백준 23741번
https://www.acmicpc.net/problem/28447
1 ~ N
까지 값으로 중복없는 조합을 만들면 된다.
{1, 2, 3}
이라고 하면 여기서 또 (i, j)
형식으로 조합을 만든다.
{1, 2}, {1, 3}, {2, 3}
으로 조합이 만들어진다.
이 2개의 조합을 만드는 과정을 DFS로 구현했다.
private static void DFS(int idx, int depth) {
if (depth == K) {
int[] temp = new int[2];
sum = 0;
check(0, 0, temp);
ans = Math.max(ans, sum);
return;
}
for (int i = idx; i < N; i++) {
comb[depth] = i;
DFS(i + 1, depth + 1);
}
} // End of DFS()
DFS()
에서 만들어진 comb[]
조합 값으로 check()
에서 2차원 elements
에서 재료를 선택한다.
private static void check(int idx, int depth, int[] temp) {
if (depth == 2) {
sum += elements[temp[0]][temp[1]];
return;
}
for (int i = idx; i < K; i++) {
temp[depth] = comb[i];
check(i + 1, depth + 1, temp);
}
} // End of check()
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, K, ans, sum;
private static int[][] elements;
private static int[] comb;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
if (K == 0) {
sb.append(0);
return sb.toString();
}
DFS(0, 0);
sb.append(ans);
return sb.toString();
} // End of solve()
private static void DFS(int idx, int depth) {
if (depth == K) {
int[] temp = new int[2];
sum = 0;
check(0, 0, temp);
ans = Math.max(ans, sum);
return;
}
for (int i = idx; i < N; i++) {
comb[depth] = i;
DFS(i + 1, depth + 1);
}
} // End of DFS()
private static void check(int idx, int depth, int[] temp) {
if (depth == 2) {
sum += elements[temp[0]][temp[1]];
return;
}
for (int i = idx; i < K; i++) {
temp[depth] = comb[i];
check(i + 1, depth + 1, temp);
}
} // End of check()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
ans = Integer.MIN_VALUE;
elements = new int[N][N];
comb = new int[K];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(st.nextToken());
elements[i][j] = num;
}
}
} // End of input()
} // End of Main class