[PS] 백준 17281번 ⚾

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

9명의 선수가 있는데, 각 선수가 각 이닝에서 어떤 결과를 낼 지 알고있다. 그리고 타순을 결정할 수 있다. 다만, 1번 선수를 4번 타자로 고정시키고 싶다.
이 때, 가능한 최대 점수를 구하는 문제이다.

1번 선수를 4번 타자로 고정시켰기 때문에 전체 경우의 수는 8! = 40320 개이다. 따라서 브루트 포스로 답을 구할 수 있다. 나머지는 구현이므로 생략하겠다.

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n, ans;
int scoring[50][9];
bool visited[9];
vector<int> bOrder;

int advance(int amount, int (&bases)[3]) {
	int score = 0;

	for (int i = 2; i >= 0; i--) {
		if (bases[i] == 0) {
			continue;
		}

		int tobe = i + amount;
		if (tobe < 3) {
			bases[i] = 0;
			bases[tobe] = 1;
		}
		else {
			bases[i] = 0;
			score++;
		}
		
	}

	if (amount == 4) {
		score++;
	}
	else {
		bases[amount - 1] = 1;
	}

	return score;
}

int gameStart() {
	int totalScore = 0;
	queue<int> bOrderCopy;

	for (int e : bOrder) {
		bOrderCopy.push(e);
	}
	
	for (int i = 0; i < n; i++) {
		int outCnt = 0;
		int bases[3]{ 0, 0, 0 };

		while (outCnt < 3) {
			int curBatter = bOrderCopy.front();
			bOrderCopy.pop();
			bOrderCopy.push(curBatter);

			switch (scoring[i][curBatter]) {
			case 0:
				outCnt++;
				break;
			default:
				totalScore += ::advance(scoring[i][curBatter], bases);
				break;
			}
			
		}
	}

	return totalScore;
}

void go(int cnt) {
	if (cnt == 9) {
		// 타순이 정해졌으니 게임을 시뮬레이션한다
		ans = max(ans, gameStart());
		return;
	}

	// 1번 선수를 4번 타자로 고정
	if (cnt == 3) {
		bOrder.push_back(0);
		visited[0] = true;
		go(cnt + 1);
		bOrder.pop_back();
		visited[0] = false;
		return;
	}

	for (int i = 1; i < 9; i++) {
		if (!visited[i]) {
			bOrder.push_back(i);
			visited[i] = true;
			go(cnt + 1);
			bOrder.pop_back();
			visited[i] = false;
		}
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> scoring[i][j];
		}
	}

	go(0);
	
	cout << ans << '\n';

	return 0;
}