[BOJ] 야구

 

[문제]

⚾는 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

각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.

출력

아인타팀이 얻을 수 있는 최대 점수를 출력한다.

예제 입력 1 

2 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0

예제 출력 1 

1

 

[풀이]

17281

맞았습니다!!

1988

288

C++14 / 수정

3323

1일 전

 

1) 홈으로 들어오는 순서의 수만큼 점수가 오르기 때문에 루에 있는 선수들의 위치를 비트로 저장한다. 

루는 1루, 2루, 3루로 총 3개의 저장공간이 필요하다. 

한번에 홈으로 들어올 수 있는 사람의 수는 3명이므로 (홈런을 쳤을 때는 홈에 있는 타자는 루에 가지 않는다.)

총 6개의 공간이 필요하다. 

0

0

0

0

0

1

-> 1루에 주자가 1명 있음 

 

1

1

1

0

0

0

-> 이번에 홈에 들어온 사람은 3명이다. 

 

2) 홈 상황 중계는 비트로 저장을 하고 선수들의 조합을 구한다. 

1번 선수는 4번 타자로 고정이 되기 때문에 makeComb()에서 4번 주자를 구할 차례가 되면 1을 넣어주고 아니면 2~9번 타자를 넣어준다. 

 

3) 9명의 타자들의 타순이 정해졌으면 이제 게임을 시작한다. 

타자들은 0, 1, 2, 3, 4 의 성적을 각각 갖고 있는데, 0은 아웃 (3아웃이면 이번 이닝이 끝남)

1은 1루 앞으로 

2는 2루 앞으로 

3은 3루 앞으로 

4는 홈런 (모든 주자들이 홈으로 온다)

 

4) 위의 비트로 생각해보면 1루는 루에 있는 주자든 이번 순서에 타자였던 선수든 1칸씩 옆으로 옮겨가야 한다. 

따라서 base << 1 을 해서 한 칸씩 앞으로 땡겨준다. 

score는 홈에 들어오는 주자가 몇명이지에 따르기 때문에 따로 함수로 빼두었다. (movemove)

 

5) 홈런의 경우에는 루에 있던 주자들의 수만큼 점수가 오른다. (전부 홈으로 들어오기 때문에)

 

6) 아웃의 경우 3번 아웃이면 이번 타순 + 1을 저장한다. (이닝이 바뀌더라도 타순은 유지)

 

7) 마지막으로 movemove는 홈에 들어오는 타자들을 보면서 점수를 높여주는 건데 

1이면 들어온 선수가 있다는 것이기 때문에 score를 증가시켜주고 

다시 0으로 바꿔준다.(반복 계산 방지)

---

 

#include <iostream>
#include <vector>
using namespace std;
//야구 
int n, inning[51][10], ans = 0, base = 0;
vector<int> sequence;
bool visited[10];
int movemove() {
    //주자들을 움직이면서 홈에 들어오는지 본다. 
    int score = 0;
    for (int i = 4; i < 7; i++) {
        if ((base & (1 << i)) > 0) {
            score++;
            base = base & ~(1 << i);
        }
        
    }
    return score;
}
int playBaseBall() {
    //게임 시작
    int out = 0, first = 1, score = 0; //1번부터 시작 -> 이닝이 끝나도 타순은 유지해야 하기때문에 따로 저장해둔다. 
    base = 0; //루에 누가 있는지 확인하기 위한 비트 변수 
    for (int i = 1; i <= n; i++) 
    {
        int idx = first;
        //sequence에 저장된 순서대로 야구를 한다. 
        while(1) {
            //3아웃이 될 때까지 현재 이닝을 계속한다. 
            int now = inning[i][sequence[idx]];
            if (now == 1) {
                //안타 
                base++;
                base = base << 1;
                score += movemove();
            }
            else if (now == 2) {
                //2루타 
                base++;
                base = base << 2;
                score += movemove();
            }
            else if (now == 3) {
                //2루타 
                base++;
                base = base << 3;
                score += movemove();
            } 
            else if (now == 4) {
                base++;
                for (int k = 0; k <4; k++) {
                    if ((base & (1<<k)) > 0) {
                        //루에 타자가 있으면 무조건 점수가 올라간다. 
                        score += 1;
                    }
                } //for k
                base = 0;
            }
            else if (now == 0) {
                //아웃 
                out++;
                if (out == 3) {
                    //이닝 종료 
                    out = 0;
                    first = idx + 1;
                    if (first > 9) first = 1;
                    base = 0;
                    break;
                }
            }
            idx++;
            if (idx > 9) idx = 1;
        } //while 
    }
    return score;
}
void makeComb(int cur) {
    if (cur > 9) {
        //타순을 다 정함
        int res = playBaseBall();
        if (ans < res) ans = res;
        return;
    }
    if (cur == 4) {
        sequence.push_back(1);
        visited[1] = true;
        makeComb(cur+1);
        sequence.pop_back(); //백트래킹
    }
    else {
        for (int i = 2; i <= 9; i++) {
            //1번 타자를 제외한 사람들을 넣어준다. 
            if (!visited[i]) {
                sequence.push_back(i);
                visited[i] = true;
                makeComb(cur + 1);
                visited[i] = false;
                sequence.pop_back();
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    
    for (int i =1; i <= n; i++ ) {
        for (int j = 1; j <= 9; j++) {
            cin >> inning[i][j];
        }
    }
    //input
    sequence.push_back(-1);
    //모든 조합을 구한다. (단, 1번 타자는 항상 4번 순서 )
    makeComb(1);
    cout << ans << '\n';
    return 0;
}

 

[넥퍼뮤 사용 ]

   /*
        최상의 타순을 정해야 한다. 단, 1번은 4번 타자 
        (아웃과 홈런을 적절히 섞어야 한다. 4번의 성적이 홈런인 경우에는 앞쪽에 최대한 많은 사람들을 루에 올려두고
        아닌 경우에는....)
        순서가 이닝이 끝난 후에도 유지된다는 걸 유의해야 한다. (이닝이 끝나면 루에는 아무도 없다.)
     */
    vector<int> entry;
    for (int i = 1; i <= 9; i++)
    {
        if (i == 4)
            continue;
        entry.push_back(i);
    }
 
    do
    {
        for (int i = 1; i <= 8; i++)
        {
            check[i] = entry.at(i - 1);
        }
        for (int i = 1; i <= n; i++)
        {
            lineUp[i][4] = arr[i][1];
            for (int j = 2; j <= 9; j++)
            {
                lineUp[i][check[j - 1]] = arr[i][j];
            }
        }
 
        score = 0;
        cal_score();
        //구한 조합으로 점수를 구한다.
 
        if (MAX < score)
            MAX = score;
 
    } while (next_permutation(entry.begin(), entry.end()));