백준 17281 - 야구 게임⚾

문제링크

• 백준 17281

문제설명

• 9명으로 이루어진 두 팀이 야구 게임을 진행한다.
• 총 N이닝 동안 게임을 진행해야 하고, 한 이닝에 3아웃이 발생하면 이닝이 종료되고 공격과 수비를 교대한다.
• 경기 시작 전 타순을 정해야 하고, 경기 중에는 타순을 변경할 수 없다.
• 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자부터 다시 타석에 선다.
• 타순은 이닝이 변경되어도 유지되어야한다. 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.
• 공을 쳐서 얻는 결과는 다음과 같다.
  • 안타(1): 타자와 모든 주자가 한 루씩 진루한다.
  • 2루타(2): 타자와 모든 주자가 두 루씩 진루한다.
  • 3루타(3): 타자와 모든 주자가 세 루씩 진루한다.
  • 홈런(4): 타자와 모든 주자가 홈까지 진루한다.
  • 아웃(0): 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.
• 선수는 1번부터 9번까지 번호가 있고, 1번 선수는 4번타자로 고정한 채 다른 선수의 타순을 모두 결정해야 한다.
• 각 선수가 각 이닝에서 어떤 결과를 얻는지가 주어질 때, 가장 많은 득점을 하는 타순을 찾고 그 때의 득점을 구하라.

문제접근

• 1번 선수는 4번 타자로 고정이 되어 있으므로, 2번~9번 선수들을 1~3번 타자, 5~9번 타자에 배치를 해야 한다.
• 타순을 구하는 경우의 수는 백트래킹을 활용하여 순열을 구하였고, 타순이 완성되면 모든 이닝을 수행한다.
• 각 이닝마다 선수들의 결과는 table[inning][number] 배열로 관리하였다.
• 주자들의 상태를 파악하기 위한 runner[4] 배열을 만들어서 1루~3루에 주자가 있는지 확인하고, 타자의 결과에 따라 움직일 수 있도록 구현했다.
• 주자들이 움직이고 나면 타자도 움직여야 한다는 점에 주의하자.

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;

int N;
int cand[9]; // cand[8]=1 : 4번 타자는 1번 선수로 고정
bool visited[8] = { false, };
int player[8] = { 2, 3, 4, 5, 6, 7, 8, 9 };
int table[51][10]; // 1번 선수부터 9번 선수까지 이닝별 결과

int playGame() {
	// 타순 설정
	int hitPlayers[10];
	for (int i = 0; i < 3; i++) {
		hitPlayers[i + 1] = cand[i];
	}
	// 4번 타자 고정
	hitPlayers[4] = cand[8];
	for (int i = 3; i < 8; i++) {
		hitPlayers[i + 2] = cand[i];
	}

	int runner[4] = { 0, 0, 0, 0 }; // 주자 상태
	int ret = 0;
	int idx = 1;
	for (int inning = 1; inning <= N; inning++) {
		int outCnt = 0;
		memset(runner, 0, sizeof(runner));
		while (true) {
			int number = hitPlayers[idx++];
			int status = table[inning][number];
			// 다음 타순 설정. out count 계산 및 탈출 조건
			if (idx == 10) idx = 1;
			if (status == 0) outCnt++;
			if (outCnt == 3) break;
			
			if (status == 1) {
				// 주자 이동
				for (int i = 3; i >= 1; i--) {
					if (i >= 3 && runner[i]) {
						ret++;
						runner[i] = 0; // 3루수는 들어옴
					}
					else if (runner[i]) {
						runner[i + 1] = 1;
						runner[i] = 0;
					}
				}
				runner[1] = 1; // 타자 이동
			}
			else if (status == 2) {
				for (int i = 3; i >= 1; i--) {
					if (i >= 2 && runner[i]) {
						ret++;
						runner[i] = 0;
					}
					else if (runner[i]) {
						runner[i + 2] = 1;
						runner[i] = 0;
					}
				}
				runner[2] = 1;
			}
			else if (status == 3) {
				for (int i = 3; i >= 1; i--) {
					if (runner[i]) {
						ret++;
						runner[i] = 0;
					}
				}
				runner[3] = 1;
			}
			else if (status == 4) {
				for (int i = 3; i >= 1; i--) {
					if (runner[i]) ret++;
					runner[i] = 0;
				}
				ret++;
			}
		}
	}
	return ret;
}

int setPlayer(int cnt) {
	if (cnt == 8) {
		return playGame();
	}
	
	int ret = 0;
	for (int i = 0; i < 8; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		cand[cnt] = player[i];
		ret = max(ret, setPlayer(cnt + 1));
		visited[i] = false;
	}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int num = 1; num <= 9; num++) {
			scanf("%d", &table[i][num]);
		}
	}
	cand[8] = 1;
	printf("%d\n", setPlayer(0));
}