[Baekjoon] 3980_선발 명단

Gold V

문제(출처: https://www.acmicpc.net/problem/3980)

---

< 선발 명단 >

 

문제 풀이 

 

포지션에 선수를 배치할 수 있는 모든 경우를 고려하여 능력치의 합의 최댓값을 구한다.

 

 

 my solution (Java)

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

public class _3980_ { // 선발 명단
	static int arr[][], answer[], result;
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int c = Integer.parseInt(bf.readLine());

		arr = new int[11][11];
		answer = new int[11];
		visited = new boolean[11];

		for (int i = 0; i < c; i++) {
			result = 0;
			for (int j = 0; j < 11; j++) {
				st = new StringTokenizer(bf.readLine());
				for (int k = 0; k < 11; k++) {
					arr[j][k] = Integer.parseInt(st.nextToken());
				}
			}
			team(0);
			bw.write(result + "\n");
		}
		bw.flush();
	}

	private static void team(int idx) {
		if (idx == 11) {
			int sum = 0;
			for (int i = 0; i < 11; i++) {
				sum += answer[i];
			}
			result = Math.max(result, sum);
			return;
		}
		for (int i = 0; i < 11; i++) {
			if (!visited[i] && arr[i][idx] > 0) {
				visited[i] = true;
				answer[idx] = arr[i][idx];
				team(idx + 1);
				visited[i] = false;
			}
		}
	}
}

변수)
c : 테스트 케이스 개수
arr : 선수의 능력
answer : 각 포지션에 배치한 선수의 능력
visited : 선수 배치 여부

 

테스트 케이스 개수를 입력받는다. 테스트 케이스 개수만큼 다음 과정을 반복한다.

 

1) 11명의 능력을 입력받아 arr 배열에 저장한다.

2) 각 포지션에 선수를 배치하기 위해 team 함수를 호출한다.

3) 능력치의 합의 최댓값을 출력한다.

 

team (int idx)

1) idx가 11이면 모든 포지션에 선수를 배치했단 뜻이므로 능력치의 합을 구한 후 최댓값인지 판단하고 종료한다.

2) idx번째 포지션에 선수를 배치하기 위해 11명의 선수를 둘러보며 아직 배치하지 않은 선수이며 능력치가 0보다 크다면 선수를 배치한다. 그다음 idx+1번째 포지션에 선수를 배치하기 위해 team(idx+1)을 호출한다. idx번째 포지션에 다른 선수를 배치할 수 있는 경우도 있으므로 배치 여부를 되돌린다.

---

---