백준 3980번: 선발 명단

문제 설명

• https://www.acmicpc.net/problem/3980
• 합이 가장 높은 조합을 구하는 문제입니다.

접근법

• 백트래킹을 활용해 풀 수 있습니다.

정답

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

public class Main {
	static int maxVal;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int[][] board = new int[11][11];
			for (int i = 0; i < 11; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 11; j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			maxVal = 0;
			BackT(0, 0, board, new boolean[11]);
			System.out.println(maxVal);

		}

	}

	public static void BackT(int depth, int answer, int[][] board, boolean[] v) {
		if (depth == 11) {
			maxVal = Math.max(maxVal, answer);
			return;
		}

		for (int i = 0; i < 11; i++) {
			if (board[i][depth] == 0 || v[i]) continue; // i번째 선수의 depth포지션 능력치가 0이거나 이미 i번째 선수를 활용했으면 패스
			answer += board[i][depth];
			v[i] = true;
			BackT(depth + 1, answer, board, v);
			v[i] = false;
			answer -= board[i][depth];
		}
	}

}