BOJ-17281 ⚾
필요한 지식
-
시뮬레이션
-
조합
접근
-
선수들을 4번째 자리를 제외하고 가능한 모든 선수배치 방법을 구한다.
-
그 선수 배치에 따른 점수를 계산한다.
-
모든 선수배치방법에 따라 결과의 최대값을 저장하며 반복한다.
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;
}
Author And Source
이 문제에 관하여(BOJ-17281 ⚾), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hschoi1104/BOJ-17281저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)