백준 17281번 ⚾ C++ 백트래킹, 구현, 시뮬레이션

리뷰

 

백트래킹 + 구현 + 시뮬레이션 문제, 시간 분배를 잘 해줘야 한다.

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

 

문제 풀이

1. 이닝의 수 n값을 받아오고 2차 정수 배열 inning에 i번째 이닝에 j번 타자가 치는 정보를 받아온다.
2. 빈 벡터 temp를 초기화 하고 dfs를 통해 완전 탐색을 돌려준다.
3. dfs의 매개변수로는 현재 타자의 수 level과 타자의 번호를 저장한 벡터 turn을 받아준다.
4. level이 9 즉, 9명의 타자가 모두 모아졌을때가 기저조건이 되며 simul함수를 호출하고 리턴한다.
5. level이 3 즉, 4번 타자의 정보를 받아올때는 0번 인덱스 (1번타자)를 추가해 주고 리턴한다.
6. 1 ~ 8인덱스 즉, 2 ~ 9번 타자가 level번째 타자가 되는 모든 경우를 탐색하며 재귀를 호출해준다.
7. 기저조건에 달했을 때 simul 함수에는 타자의 순서 정보가 담긴 turn 벡터를 매개변수로 전달해 준다.
8. 시뮬레이션이 시작된다면 우선 0번 인덱스가 첫 타자가 될 것이며, 점수는 0일때 부터 시작한다.
9. 각 이닝을 참고해야 하므로 n번 for문을 돌려주고 out과 베이스 정보는 빈 상태로 시작한다.
10. out카운트가 3 이하일 동안 while루프를 돌려준다.
11. index가 9 즉, 타자가 한 사이클이 돌았다면 index를 다시 0으로 초기화 해준다.
12. 만약 현재 이닝에 index번 타자가 0일 경우 즉, 아웃일 경우 아웃카운트와 인덱스를 올린 후 continue 처리해 준다.
13. run 변수에 현재 타자가 친 안타를 기록해 준다.
14. 만약 run이 4 즉, 타자가 홈런을 쳤다면 본인의 타점으로 point를 증가시키고 베이스에 존재하는 모든 타자들의 수 만큼 point를 증가시켜 준다, 이때 베이스는 다시 0으로 초기화 해준다.
15. run이 4가 아니라면 베이스를 거꾸로 탐색하여 i번째 베이스에 타자가 있다면, i번째 베이스를 0으로 만들어 주고 i + run 값이 4 이상이라면 point를 증가시킨다, 아니라면 i + run 베이스에 1을 기록해 준다.
16. 추가로, base의 run번째 인덱스를 1을 넣어 타자가 진루한 경우를 기록해 준다.
17. 시뮬레이션이 종료되고 ans값을 최대값으로 계속 갱신해 준다. 모든 루프가 종료되면 ans값을 출력해 준다.

 

참고 사항

처음엔 이닝 정보를 map을 사용해 해시로 구현하려 했지만, 정수형 2차 배열이 속도가 더 빨랐다.

결국 모든 타자의 순서 경우를 확인해 주어야 하기 때문에 신박한 가지치기 최대한 최적화를 해주는게 좋아보인다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;
int n, ans = 0;
int inning[50][9];
int v[9] = { 0, };

int simul(vector<int>& turn) {
	int index = 0, point = 0;
	for (int i = 0; i < n; i++) {
		int base[4] = {0, 0, 0, 0};
		int out = 0;
		while (out < 3) {
			if (index >= 9) index = 0;
			if (inning[i][turn[index]] == 0) {
				out++;
				index++;
				continue;
			}
			int run = inning[i][turn[index]];
			if (run == 4) {
				point++;
				for (int i = 1; i < 4; i++) {
					if (base[i]) {
						base[i] = 0;
						point++;
					}
				}
			}
			else {
				for (int j = 3; j >= 0; j--) {
					if (!base[j]) continue;
					base[j] = 0;
					if (j + run >= 4) point++;
					else base[j + run] = 1;
				}
				base[run] = 1;
			}
			index++;
		}
	}
	return point;
}

void dfs(int level, vector<int>& turn) {
	if (level == 9) {
		ans = max(ans, simul(turn));
		return;
	}

	if (level == 3) {
		turn.push_back(0);
		dfs(level + 1, turn);
		turn.pop_back();
		return;
	}

	for (int i = 1; i < 9; i++) {
		if (v[i]) continue;
		v[i] = 1;
		turn.push_back(i);
		dfs(level + 1, turn);
		turn.pop_back();
		v[i] = 0;
	}
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 9; j++) {
			int a; cin >> a;
			inning[i][j] = a;
		}
	}
	vector<int> temp;
	dfs(0, temp);
	cout << ans;
}