BOJ - 선발 명단

https://www.acmicpc.net/problem/3980

3980번: 선발 명단

 

• 백트래킹을 활용한 완전 탐색 문제이다.
• 주어진 포지션의 개수와 플레이어 포지션 별 능력을 활용하여 완전 탐색 후 최대 값을 구하면 된다.

import java.io.*;
import java.util.*;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int[][] abilities;
    private static int maximumAbility;
    private static boolean[] positions;

    public static void main(String[] args) throws IOException {
        int C = Integer.parseInt(br.readLine());

        while (C-- > 0) {
            //초기화
            abilities = new int[11][11];
            positions = new boolean[11];
            maximumAbility = 0;
            for (int i = 0; i < 11; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 11; j++) {
                    abilities[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            dp(0, 0, 0);
            System.out.println(maximumAbility);
        }
    }

    private static void dp(int depth, int player, int ability) {
        if (depth == 11) {
            if (!isPositionValid()) return;
            maximumAbility = Math.max(maximumAbility, ability);
            return;
        }

        for (int i = 0; i < 11; i++) {
            if (abilities[player][i] == 0) continue;
            if (positions[i]) continue;

            positions[i] = true;
            ability += abilities[player][i];

            dp(depth + 1, player + 1, ability);

            positions[i] = false;
            ability -= abilities[player][i];
        }
    }

    private static boolean isPositionValid() {
        for (int i = 0; i < positions.length; i++) {
            if (!positions[i]) return false;
        }
        return true;
    }
}