BOJ-17281 ⚾

14417 단어 algorithmbojalgorithm

필요한 지식

  1. 시뮬레이션

  2. 조합

접근

  1. 선수들을 4번째 자리를 제외하고 가능한 모든 선수배치 방법을 구한다.

  2. 그 선수 배치에 따른 점수를 계산한다.

  3. 모든 선수배치방법에 따라 결과의 최대값을 저장하며 반복한다.

chk[i]=j : i번째 순서의 선수번호는 j이다.

game[i][j]=k : i-1 번째 이닝의 선수번호 j의 결과는 k이다.

state[i]=j : i=0 홈, i=1 1루, i=2 2루... 에 선수가 있는지 없는지 1과 0으로표시

init() : 이닝 종료시 홈과 1~3루, 아웃카운트 정보 초기화

move(int r) : r의 결과를 가지고 선수들의 움직임을 state배열에 업데이트

cal() : n개의 이닝동안 정해진 선수들의 순서로 얻을 수 있는 점수 계산

go() : 선수들의 순서를 정해줌 9명의 순서가 전부 정해졌다면 cal()함수로 계산

코드(C++)

#include <iostream>
#include <algorithm>
using namespace std;
int chk[10] = { 0,0,0,0,1 }, game[51][10], state[5], n, out = 0, ans = 0;
//주자들이 움직임
void init() {
	for (int i = 0; i < 5; i++) state[i] = 0;
	out = 0;
}
int move(int r) {
	int res = 0;
	state[0] = 1;
	for (int i = 3; i >= 0; i--) {
		if (state[i]) {
			if (i + r >= 4)	res += 1;
			else state[i + r] = 1;
			state[i] = 0;
		}
	}
	return res;
}
void cal() {
	int res = 0, t = n, pos = 1;
	for (int i = 0; i < n; i++) {//이닝
		while (1) {//선수들이 타석에 섬, out == 3까지
			if (out == 3) {
				init();
				break;
			}
			if (pos == 10) pos -= 9;
			if (!game[i][chk[pos]]) out += 1;
			else res += move(game[i][chk[pos]]);
			pos++;
		}
	}
	ans = max(ans, res);
}
void go(int pos) {
	if (pos == 10) {
		cal();
		return;
	}
	for (int i = 1; i <= 9; i++) {
		if (!chk[i]) {
			chk[i] = pos;
			go(pos + 1);
			chk[i] = 0;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) for (int j = 1; j <= 9; j++) cin >> game[i][j];
	go(2);
	cout << ans;
	return 0;
}

좋은 웹페이지 즐겨찾기