백준 3980(JAVA)

문제

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

3980번: 선발 명단

풀이

11개의 포지션에 11명의 선수를 넣어주면 된다.
모든 경우의수를 돌며 최대 값을 뽑으면된다.

단, 해당 포지션의 성능이 0이면 해당 포지션에 선수를 배치하지 못하는 가지치기 조건을 이용해 경우의 수를 대폭 줄이면 된다.

즉, 백트래킹을 통해 가지치기로 시간적 이득을 봐야만 맞을수 있는 문제이다.

너무간단한데, 테스트 횟수가 있으므로 static 변수를 사용한다면 초기화를 계속 해줘야한다. (이거 놓쳐서 2번 틀림)

코드

package training.backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main3980 {
    static int T;
    static int[][] S;
    static int[] result;
    static boolean[] visited;
    static int max = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for(int v = 0; v < T; v++){
            S = new int[11][11];
            result = new int[11];
            visited = new boolean[11];
            max = -1;

            for(int i = 0; i < 11; i++){
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for(int j = 0; j < 11; j++){
                    S[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            //포지션 11개에 각선수들을 배치하자.

            recursive(0);

            System.out.println(max);
        }
    }
    static void recursive(int m){
        if(m == 11){
            int sum = 0;
            for(int i = 0; i < 11; i++){
                sum += S[result[i]][i];
            }
            max = Math.max(max, sum);
            return;
        }

        for(int i = 0; i < 11; i++){
            if(!visited[i] && S[i][m] != 0){
                visited[i] = true;
                result[m] = i;
                recursive(m + 1);

                visited[i] = false;
            }
        }
    }
}