[BOJ-17281] 야구

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

17281번: ⚾

 

 

개인적으로 조금 어려웠던 문제였다

 

내가 해결하는데 어려움을 겪었던건

 

1. 순열을 찾는 것

 

2. 4번 타자를 1번 선수로 고정시키는 것

 

3. 각 루에 있는 선수들을 홈으로 보내는 것 정도의 처리?

 

그냥 한 마디로 모든 부분이 어려웠다..

 

어떻게 풀 지는 머릿속으로 구현이 되었던 문제인데, 실제로 코드로는 구현이 안되서 시간이 오래걸렸다.

 

만약 시험장에서 이 문제를 만났다면 못풀었을것 같다는 느낌이 들었다.

 

앞으로 순열 문제를 많이 풀어보도록 해야겠다.

 

- 문제 풀이

 

1. 입력을 받는다.

 

2. 타순을 정할 배열을 하나 만들어준다.

 

3. 타순을 정하기 위해 만든 배열의 4번째 원소에 1번 타자의 인덱스 값인 0을 집어넣어준다.

 

4. 0번 부터 모든 경우의 수를 고려하여 완탐한다.(순열로 완탐했음)

(방문하려는 노드가 4번째 원소이면 그냥 다음으로 넘겨주는 코드도 추가해준다.)

 

5. 9번째 까지 다 방문을 했으면 합을 구해준다.

(이 때, 야구에서는 3루까지 있으므로 3개짜리 배열을 만들어줬고, 선수가 각각 안타, 2루타, 3루타, 홈런, 아웃을 칠 경우에 대해 처리를 해줬다.)

 

6. 이전에 구한 합과 이번에 구한 합을 비교하고 더 큰 값으로 갱신해준다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int n, res, out;
int player[50][9];
bool visited[9];
int seq[9];

void dfs(int node) {
	if (node == 3) {
		dfs(node + 1);
		return;
	}

	if (node == 9) {

		int candi = 0;
		int index = 0;

		for (int i = 0; i < n; i++) {

			int cnt = 0;
			int j = index;
			index = 0;
			int lu[3] = { 0, };

			while (1) {
				if (cnt == 9) cnt = 0;
				j %= 9;

				if (player[i][seq[j]] == 0) {
					out += 1;

					if (out == 3) {
						index = j + 1;
						out = 0;
						break;
					}
				}

				else if (player[i][seq[j]] == 1) {
					if (lu[2] != 0) {
						lu[2] = 0, candi += 1;
					}
					if (lu[1] != 0) {
						lu[2] = 1, lu[1] = 0;
					}
					if (lu[0] != 0) {
						lu[1] = 1, lu[0] = 0;
					}
					if (lu[0] == 0) {
						lu[0] = 1;
					}
				}

				else if (player[i][seq[j]] == 2) {
					if (lu[2] != 0) {
						lu[2] = 0, candi += 1;
					}
					if (lu[1] != 0) {
						lu[1] = 0, candi += 1;
					}
					if (lu[1] == 0) {
						lu[1] = 1;
					}
					if (lu[0] != 0) {
						lu[2] = 1, lu[0] = 0;
					}
				}

				else if (player[i][seq[j]] == 3) {
					if (lu[2] != 0) {
						lu[2] = 0, candi += 1;
					}
					if (lu[2] == 0) {
						lu[2] = 1;
					}
					if (lu[1] != 0) {
						lu[1] = 0, candi += 1;
					}
					if (lu[0] != 0) {
						lu[0] = 0, candi += 1;
					}
				}

				else if (player[i][seq[j]] == 4) {
					if (lu[2] != 0) {
						lu[2] = 0, candi += 1;
					}
					if (lu[1] != 0) {
						lu[1] = 0, candi += 1;
					}
					if (lu[0] != 0) {
						lu[0] = 0, candi += 1;
					}
					candi += 1;
				}
				j += 1;
				cnt += 1;
			}
		}

		if (candi > res) res = candi;

		return;
	}

	for (int i = 1; i < 9; i++) {
		if (visited[i]) continue;
		seq[node] = i;
		visited[i] = true;
		dfs(node + 1);
		visited[i] = false;
	}
}

int main(void) {

	scanf("%d", &n);

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

	seq[3] = 0;
	dfs(0);

	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}