[BOJ] #17281 _ 야구

[야구] https://www.acmicpc.net/problem/17281

17281번: ⚾

야구의 룰을 알면 쉽게 이해할 수 있다.

야구의 룰을 그대로 시뮬레이션하여 구현하는 문제이다.

 

처음에는 vector를 사용하여 뒤에 3개의 값으로 1, 2, 3루로 판단하여 구현하였으나, 시간 초과가 발생하였다.

시간 복잡도를 잘 생각해야 한다.

모든 경우의 수를 체크해야만 하기 때문에 여기서 걸리는 시간은 어쩔 수 없다.

찾아보니 벡터와 큐의 push연산이 느리다는 말이 있어 벡터대신 배열로 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>
#define MAX 50

using namespace std;

int inning, chk[9], order[9], max_score;
int player[MAX][9];

void solve(int cnt);
int play();
int main() {
	scanf("%d", &inning);

	for (int i = 0; i < inning; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &player[i][j]);
		}
	}

	chk[3] = 1;
	order[3] = 0;
	for (int i = 0; i < 9; i++) {
		if (i == 3) continue;
		order[i] = 1;
		chk[i] = 1;
		solve(2);
		chk[i] = 0;
	}

	printf("%d\n", max_score);
	return 0;
}

void solve(int cnt) {
	if (cnt >= 9) {
		max_score = max(max_score, play());
		return;
	}
	for (int i = 0; i < 9; i++) {
		if (chk[i]) continue;
		order[i] = cnt;
		chk[i] = 1;
		solve(cnt + 1);
		chk[i] = 0;
	}
}

int play() {
	int out, score = 0, turn = 0;
	int ground[3];

	for (int i = 0; i < inning; i++) {
		out = 0;
		for (int j = 0; j < 3; j++) ground[j] = 0;

		while (1) {
			if (player[i][order[turn]] == 0) out++;
			else if (player[i][order[turn]] == 1) {
				if (ground[2]) {
					ground[2] = 0;
					score++;
				}
				for (int j = 1; j >= 0; j--) {
					if (ground[j]) {
						ground[j] = 0;
						ground[j + 1] = 1;
					}
				}
				ground[0] = 1;
			}
			else if (player[i][order[turn]] == 2) {
				for (int j = 2; j > 0; j--) {
					if (ground[j]) {
						ground[j] = 0;
						score++;
					}
				}
				if (ground[0]) {
					ground[0] = 0;
					ground[2] = 1;
				}
				ground[1] = 1;
			}
			else {
				for (int j = 2; j >= 0; j--) {
					if (ground[j]) {
						ground[j] = 0;
						score++;
					}
				}
				if (player[i][order[turn]] == 3) ground[2] = 1;
				else score++;
			}

			turn = (turn + 1) % 9;
			if (out >= 3) break;
		}
	}

	return score;
}