[BOJ] 17281 : 야구 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. Backtracking 을 이용해 가능한 모든 타순에 대해서 게임을 진행합니다. ( 이때, 1번 선수는 4번 타자로 선발된 경우만 게임을 진행합니다. )

2. 게임은 N 이닝 동안 현재 주자 상태와 현재 타석에 있는 타자의 결과에 따라서 score를 계산해주면 됩니다.

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

using namespace std;

int N, result[50][9] = {}, ans = -1;

int startGame(vector<int> batting) {
	int score = 0, batter = 0, out = 0;
	for (int i = 0; i < N; i++) {
		out = 0;
		bool runner[3] = {};
		while (out < 3) {
			if (result[i][batting[batter]] == 0)
				out++;
			else {
				// 기존에 있던 주자들
				for (int j = 2; j >= 0; j--) {
					if(runner[j]){
						if (j + result[i][batting[batter]] >= 3)
							score++;
						else
							runner[j + result[i][batting[batter]]] = true;
						runner[j] = false;
					}
				}
				// 타자
				if (result[i][batting[batter]] == 4)
					score++;
				else
					runner[result[i][batting[batter]] - 1] = true;
			}

			batter = (batter + 1) % 9;
		}
	}
	return score;
}

void backTracking(vector<int> batting, bool check[9]) {
	if (batting.size() == 9) {
		if(batting[3] == 0)
			ans = max(ans, startGame(batting));
		return;
	}
	for(int i = 0; i < 9; i++)
		if (!check[i]) {
			batting.push_back(i);
			check[i] = true;
			backTracking(batting, check);
			check[i] = false;
			batting.pop_back();
		}
	return;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 9; j++)
			cin >> result[i][j];

	vector<int> batting;
	bool check[9] = {};
	for (int i = 0; i < 9; i++) {
		batting.push_back(i);
		check[i] = true;
		backTracking(batting, check);
		check[i] = false;
		batting.pop_back();
	}
	cout << ans;
	return 0;
}

---