[BOJ] 3980. 선발 명단 (backtracking, bruteforcing)

Gold V

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

3980번: 선발 명단

챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다.

오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다.

수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100까지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.

이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오. 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

 

input:

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 C가 주어진다.
• 각각의 케이스는 11줄로 이루어져 있고, i번 줄은 0과 100사이의 11개의 정수 sij를 포함하고 있다. sij는 i번선수가 j번 포지션에서 뛸 때의 능력이다. 모든 선수에게 적합한 포지션의 수는 최대 5개이다. (능력치가 0보다 크다)

output:

• 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다.

 

---

Idea :

• 팀의 능력치가 최대가 되는 배치 조합을 찾아야 함
• 각각의 위치에 어떤 선수를 배치하느냐에 따라 팀의 능력치가 달라짐
• 순열 문제 → DFS

Code :   

#include <iostream>

using namespace std;

int stat[11][11] = {};  // input으로 주어지는 포지션의 따른 각 선수의 능력치
int perm[11] = {};      // 선수 배치 조합
int max_stat = 0;       // 팀 능력치 최댓값

/* solve: 선수 배치 조합을 구하고, 팀 능력치의 최댓값을 구하는 함수 
 *
 * parameters - player: 0-10 번 중 포지션을 배치할 선수 번호
 *            - visited: 이미 선수를 배치한 포지션 정보
 *            - team_stat: player-1까지 배치했을 때의 팀 능력치 
 * no return
 */
void solve(int player, int visited, int team_stat) {
	if (player == 11) {	// 모든 선수를 배치했을 때
		if (team_stat > max_stat) max_stat = team_stat;
		return;
	}

	for (int pos=0; pos<11; pos++) {
		if ((visited & (1 << pos)) != 0) continue;  // 이미 선수를 배치한 포지션일 경우
		if (stat[player][pos] == 0) continue;       // 해당 포지션에서의 선수의 능력치가 0인 경우
		solve(player+1, visited | (1 << pos), team_stat + stat[player][pos]);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	int TC;
	
	cin >> TC;
	while (TC--) {
		/* init & input */
		for (int i=0; i<11; i++) {
			for (int j=0; j<11; j++)
				cin >> stat[i][j];
		}
		max_stat = 0;

		/* solve */
		solve(0, 0, 0);
		cout << max_stat << "\n";
	}

}

 

---

Result : 

메모리: 2020 KB,  시간: 4 ms

 

Review :