문제
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.
두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.
공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.
타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.
-
안타: 타자와 모든 주자가 한 루씩 진루한다.
-
2루타: 타자와 모든 주자가 두 루씩 진루한다.
-
3루타: 타자와 모든 주자가 세 루씩 진루한다.
-
홈런: 타자와 모든 주자가 홈까지 진루한다.
-
아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.
한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.
입력
첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.
- 안타: 1
- 2루타: 2
- 3루타: 3
- 홈런: 4
- 아웃: 0
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
예시 입력 및 출력
입력
2
4 3 2 1 0 4 3 2 1
1 2 3 4 1 2 3 4 0
출력
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N;
int hitTable[50][9]; // 안타 정보
int entry[9];
vector<int> field;
// 현재 엔트리로 얻는 점수 구하는 함수
int findMaxScore() {
int out = 0; // 아웃 횟수
int turnIdx = 0; // 현재 타자 idx
int score = 0;
// 0이닝부터 N이닝 까지
for (int inning = 0; inning < N; inning++) {
// 이닝이 바뀌면 필드와 out 카운트 초기화
field.clear();
out = 0;
// 3아웃 아니면 계속 진행
while (out < 3) {
// 현재 선수 아웃
if (hitTable[inning][entry[turnIdx]] == 0) {
out++;
}
// 현재 선수 안타
else {
field.push_back(0); // 선수 1명 출루
int hitscore = hitTable[inning][entry[turnIdx]]; // 몇루타인지 저장
// 현재 필드에 있는 선수들 모두 진루
for (int i = 0; i < field.size(); i++)
field[i] += hitscore; // 진루
// 현재 필드에 선수가 있고 3루를 넘어가면
while (!field.empty() && field[0] >= 4) {
field.erase(field.begin()); // 홈으로 들어옴
score++; // +1점
}
}
// 다음 선수로
if (turnIdx == 8)
turnIdx = 0;
else
turnIdx++;
}
}
// 최종 점수 반환
return score;
}
// 엔트리 만들기 완전탐색
int makeEntry(int entryNum) {
// entry가 완성되면 findMaxScore() 호출
if (entryNum == 9) {
field.clear(); // 이전 엔트리로 야구를 했기때문에 필드를 초기화해주어야함
return findMaxScore(); // 점수 구하기
}
// 3번타자는 0번선수 고정
if (entryNum == 3) {
entry[3] = 0;
return makeEntry(entryNum + 1);
}
int res = 0;
bool flag;
for (int i = 1; i < 9; i++) {
// 0번 선수 제외, 이전 entry에 넣으려는 선수가 있는지 검사해 flag 저장
flag = true;
for (int j = 0; j < entryNum; j++) {
if (i == entry[j])
flag = false;
}
// 없다면 선수를 해당 entry에 넣고 다음 entry 작성
if (flag) {
entry[entryNum] = i;
res = max(res, makeEntry(entryNum + 1));
}
}
return res;
}
int main() {
memset(entry, -1, sizeof(entry));
cin >> N;
for (int inning = 0; inning < N; inning++)
for (int player = 0; player < 9; player++)
cin >> hitTable[inning][player];
cout << makeEntry(0) << endl;
return 0;
}문제 풀이
- 총 9번 함수 호출 -> 0~8번 엔트리 구성, 9번 함수에서 점수 구하는 함수 호출 후 점수 반환
- 함수에서 1~8번 선수가 이전까지의 엔트리에 있는지 검사하고 없으면 현재 idx 엔트리에 넣는다 -> 다음 재귀함수를 호출한다.
2. 점수 구하기
- 총 N이닝 진행
- out count 를 설정하여 선수의 hitTable 값이 0 이면 count++ -> 현재 이닝에서 count==3이 되면 현재 이닝을 종료하고 다음 이닝으로 넘어간다.
- 현재 선수가 안타를 치면 -> field를 나타내는 vector에 0을 삽입하고 선수의 타점에 따라 vector의 모든원소(필드에 있는 모든 선수의 위치)+ 타점 해준다.
- vector를 순회하여 값이 4이상(3루를 지남)이면 삭제하고 score++한다.