백준 23741번
https://www.acmicpc.net/problem/28447

문제

---

생각하기

---

• DFS, 백트래킹 문제이다.

동작

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