[백준]JAVA - 3980번: 선발 명단

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

3980번: 선발 명단

🔶 풀이

11명 선수의 포지션 별 능력이 입력된다.

포지션 별로 중복되지 않은 선수 11명을 뽑아서 최대 점수를 구하라.

 

완전 탐색으로 진행하게 되면 경우의 수는 11! (39,916,800)로 시간 초과가 발생할 수 있다.

때문에 백트래킹을 사용해서 시간 복잡도를 줄여야한다.

 

위 문제에서 능력치가 0인 경우에는 해당 포지션에 설 수 없다고 했다. 또한, 이미 선발된 선수가 또 다시 선발될 수 없으므로 selected[] 배열로 선발 여부를 처리해준다.

for (int i=0; i<11; i++) {
    if (!selected[i] && ability[person][i] > 0) {
        selected[i] = true;
        getSum(person+1, tmpSum+ability[person][i]);
        selected[i] = false;
    }
}

선발된 선수 인원을 한 명씩 증가시키면서 재귀함수를 구현하다가 선발 선수 11명을 채웠을 때 최고 능력치합을 구해주면 된다.

 

 

<최종코드>

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

public class Main {
    static boolean[] selected;
    static int[][] ability;
    static int maxScore;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int N = Integer.parseInt(br.readLine()); // 테스트 케이스
		
        while (N-- > 0) {
            ability = new int[11][11];  // 포지션 별 능력
            selected = new boolean[11]; // 방문 여부
            maxScore = 0;
			
            for (int i=0; i<11; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j=0; j<11; j++) {
                    ability[i][j] = Integer.parseInt(st.nextToken());
                }
            }
			
            getSum(0, 0);
            System.out.println(maxScore);
        }
    }
	
    /**
     * 
     * @param person 현재 선택해야하는 선수 idx
     * @param tmpSum 
     */
    public static void getSum(int person, int tmpSum) {
        
        // 11명을 다 뽑았을 경우
        if (person == 11) {
            maxScore = Math.max(maxScore, tmpSum);
            return;
        }
		
        for (int i=0; i<11; i++) {
            if (!selected[i] && ability[person][i] > 0) {
                selected[i] = true;
                getSum(person+1, tmpSum+ability[person][i]);
                selected[i] = false;
            }
        }
    }
}