야구선수 별로 몇 이닝에 몇루타를 치는지 알고 있는 상황에서 낼 수 있는 최대 점수를 구하는 문제이다.
등번호 1번의 선수를 4번타자로 고정시켜야 한다는 특이점이 있다.
문제 해결 전략
우선 각 등번호의 야구 선수들이 이닝당 몇루타를 치는지 배열에 저장 해 둔다.
1. 야구선수 순열 정하기
순열을 통해 가능한 모든 야구선수 순서를 정해서 모든 경우에 대해 낸 점수를 구해서 최대값을 고른다.
next_permutation()을 통해 1번부터 9번까지 야구선수의 모든 순열을 구하는데, 1번을 4번타자에 고정해야 해서 v[3] != 1 일 때 continue 를 해 준다.
2. 한 이닝당 낸 점수 구하기
기존의 야구와 달리 몇루타를 치면 무조건 진루를 해야 한다.
따라서 베이스를 5개 할당해서 0번에는 현재 타자, 1~3번에는 진루 상태, 4번에는 홈으로 들어온 주자를 누적해 준다.
예를들어 현재 타자가 3루타를 치면 모든 베이스에서 1칸씩 진루하며 총 세번 일어나야 한다.
진루를 하면 다음 베이스에 +1을 해 주고 기존의 베이스에는 주자가 없기 때문에 0으로 해 준다.
그리고 출루를 한 사람을 4번 베이스에 누적해 준다.
아웃 세번이면 공격이 종료 된다.
주의할 점
타자와 루수 인덱스를 참조하기 위해 1번부터 했는데, 순열 구하기 위해 사용한 벡터에서는 0번부터 할당을 했다.
그래서 이 부분을 잘 조율 했어야 했다.
그리고 위에서 말한 인덱스 처리 때문에 1번 타자가 4번타자가 되어야 하므로 v[3] != 1로 해야 했는데 실수로 v[4] != 1로 하는 바람에 이거 찾느라 시간을 오래 사용해버렸다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int arr[51][10];
vector<int> v;
vector<pair<int,int>> inning(int start, int in){
int o_cnt = 0;
int base[5] = {0,0,0,0,0};
int i = start-1;
for(;;i++){
if(i == 9)
i = 0;
base[0] = 1;
int roo = arr[in][v[i]];
if(roo == 0) {
o_cnt++;
if(o_cnt == 3)
break;
continue;
}
for(int k=0;k<roo;k++) {
for (int j = 3; j >= 0; j--) {
base[j + 1] += base[j];
base[j] = 0;
}
}
}
vector<pair<int,int>> tmp;
tmp.push_back(make_pair(i+2,base[4]));
return tmp;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=9;j++){
cin >> arr[i][j];
}
}
for(int i=1;i<=9;i++)
v.push_back(i);
int mx = -1;
do{
if(v[3] != 1)
continue;
vector<pair<int,int>> s;
int score = 0;
s.push_back(make_pair(1,0));
for(int i=1;i<=n;i++){
int start = s[0].first;
score += s[0].second;
s = inning(start, i);
}
score += s[0].second;
mx = max(mx,score);
}while(next_permutation(v.begin(), v.end()));
cout << mx << "\n";
return 0;
}