[BOJ] 17281. ⚾

https://www.acmicpc.net/problem/17281

17281번: ⚾

예전에 문제를 처음 봤을 때는 시간 안에 제대로 풀지 못했던 문제이다

비트 마스크를 이용해서 풀면 조금 더 쉽게 풀 수 있는 문제였다

 

먼저,

9명의 선수들의 가능한 모든 타순을 구해보고 경기를 시작하여 점수를 계산한 뒤 가장 높은 득점을 얻는 경우의 득점을 구해주면 된다. 선수를 고를 때, 문제에서 4번 타자는 1번 선수로 고정되어 있으므로 이 부분만 주의해주면 된다.

 

 

선수들의 타순을 모두 정해줬다면 경기를 시작해주면 된다.

이닝수만큼 경기를 진행하고 각 이닝은 3아웃이 발생할 때까지 진행한다.

 

 

9번선수까지 모두 공격을 진행해도 아웃이 되지 않는 한 이닝은 계속 진행되므로 9번 선수 다음에는 1번선수가 경기를 하도록 잘 처리해주어야 한다. 마찬가지로 이닝이 끝나도 이닝이 끝날 때 선수의 다음 선수가 바로 이어서 다음 이닝에서 시작할 것이므로 다음 이닝을 시작할 타자의 index를 잘 저장해두어야 한다. (이때도 9번 선수 다음 1번선수가 오는 경우를 잘 처리해줘야 한다!)

 

 

이제 가장 중요한 타자가 진루했을 때  점수를 구하는 방법이다.

나는 location이라는 변수를 두고 비트 마스크를 이용하여 풀었다.

 

location = 0000000

으로 볼 때 각 자리는 다음과 같은 의미를 가지고 있다고 본다.

점수	점수	점수	3루	2루	1루	홈
0	0	0	0	0	0	0

 

 

 

각 타자가 공격을 시작할 때 먼저 location의 값에 1을 더해줘서 홈에 1이 생기도록 해준다.

그리고 

 

• 안타: location << 1을 해주면 주자들이 왼쪽으로 한 루씩 진루한다.
• 2루타: location << 2를 해주면 주자들이 왼쪽으로 두 루씩 진루한다.
• 3루타: location << 3을 해주면 주자들이 왼쪽으로 세 루 씩 진루한다.
• 홈런: 현재 나와있는 모든 타자들이 모두 홈으로 돌아와서 점수를 얻을 것이므로 현재 홈, 1루, 2루, 3루에 있는 타자 들 만큼 점수를 더해준다.
• 아웃: 아웃수를 증가해주고 아웃수가 3인 경우에는 다음 이닝을 시작할 타자 인덱스를 저장해 두고 location = 0으로 만들어준다.(새로 시작해야 하기 때문에 나와있는 타자들은 모두 들어온다)

 

홈런은 위에 쓴 것처럼 바로 점수를 계산해주었고 안타에서 3루타까지는 타자가 공격을 할 때마다 점수를 계산해줘야 하는데 위의 location에서 3루보다 왼쪽으로 넘어간 경우에(홈으로 다시 들어왔다고 볼 수 있음) 점수를 얻게 된다.

 

한 번에 최대로 3만큼 움직일 수 있으므로(3루타를 친경 우) 1 << 4 에서부터 1 << 5, 1 << 6 한 위치까지만 검사해주면 되는데 해당 자리에 1이 있으면(주자가 있으면) 점수를 더해주면 된다.

 

점수를 더해줬으면 해당 선수는 나와야 하므로 location에서 해당 선수의 자리를 다시 0으로 만들어주어야 한다.

오른쪽에서부터 i번째 위치의 1을 제거해주기 위해서는

 

 location = location & ~(1 << i);

 

이런 식으로 & ~ 연산을 해주면 된다.

 

 

구체적으로 예를 들어 보자

 

0001100 인 상태에서 (2루와 3루에 타자가 있음)

홈에 다음 타자가 오면 +1을 해줘서

0001101 이 되고 이 타자가 3루타를 치면

0110100 이 된다.

 

이때 0110100 빨간 부분의 점수를 계산해주고 1을 없애주면 된다.

 

 

이 경우에는 1<<4 일 때

  0110100

&0010000

  0010000 으로 0이 아닌 값이 나와서 점수를 1 증가시켜준다.

 

그리고 다시

  0110100

&1101111  // ~(1<<4)와 &연산을 해줘서 1을 없애준다.

  0100100 

 

마찬가지로 1 << 5일 때도 점수를 더해주고 1을 없애줄 수 있고

1 << 6 인경우는 0이므로 (주자가 없으므로) 계산해주지 않는다.

#include <iostream>
#include <vector>
using namespace std;
 
int info[51][10];
bool check[10];
int n;
int ans;
int location;
 
vector<int> order;
 
 
//타자가 진루하였을때의 점수를 계산하여 return
int go() {
 
    int point = 0;
 
    for (int i = 4; i < 7; i++) {
        if (location & (1 << i)) {
            point += 1;
 
            //점수에 더해줬으면 해당 위치의 1을 제거
            location = location & ~(1 << i);
        }
    }
 
    return point;
}
 
 
//경기 시작
int start() {
    int out = 0;
    int point = 0;
    int first = 1;
 
 
    //주자의 위치를 표현할 변수
    location = 0;
 
 
    //이닝수만큼 진행
    for (int i = 1; i <= n; i++) {
 
        //각각의 타자들 공격
        int j = first;
        while (true) {
 
            //j번 타자의 i번째 이닝에서의 점수
            int result = info[i][order[j]];
 
            if (result == 1) {
                location += 1;
                location = location << 1;
                point += go();
            }
            else if (result == 2) {
                location += 1;
                location = location << 2;
                point += go();
            }
            else if (result == 3) {
                location += 1;
                location = location << 3;
                point += go();
            }
            else if (result == 4) {
                location += 1;
                for (int k = 0; k < 4; k++) {
                    if (location & (1 << k)) {
                        point += 1;
                    }
                }
 
                //홈런이므로 모두 나간다
                location = 0;
            }
            else if (result == 0) {
                out++;
 
 
                //3아웃이면 이닝 종료
                if (out == 3) {
                    out = 0;
 
                    //다음 이닝에서 현재 순서의 다음타자부터 시작
                    first = j+1;
                    if (first == 10) first = 1;
 
                    //현재 이닝이 끝났으므로 주자를 모두 없앤다.
                    location = 0;
                    break;
                }
            }
 
 
            //다음타자
            j++;
            if (j == 10) j = 1;
        }
 
 
    }
 
 
 
    //이번에 선택한 타순으로 얻는 득점을 리턴 
    return point;
 
}
 
 
//타순을 정해준다. index번째에 공격할 타자를 정한다.
void select(int index) {
    //9명의 타순을 모두 정한 경우 경기 시작
    if (index > 9) {
        //해당 순서에서 진행한 경기의 점수를 받아와서 최댓값과 비교
        int tmp = start();
        if (ans < tmp) ans = tmp;
        return;
    }
 
 
    //4번타자는 무조건 1번 선수
    if (index == 4) {
        order.push_back(1);
        check[1] = true;
        select(index + 1);
        order.pop_back();
    }
    else {//1번 선수를 제외한 모든 선수를 index번째 순서에 넣어본다.
        for (int i = 2; i <= 9; i++) {
            if (check[i]) continue;
 
            //index번째에 i번 타자를 선택하고 다음 타자를 정해준다.
            order.push_back(i);
            check[i] = true;
            select(index + 1);
 
            //다음 경우를 위해서 false로 바꿔주고 벡터에서 빼준다.
            check[i] = false;
            order.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 >> info[i][j];
        }
    }
 
 
    //1부터 시작할 것이므로 0번째에 자리 채워 준다 (그냥 0 넣어줌)
    order.push_back(0);
 
    //탐색 시작
    select(1);
 
    cout << ans << '\n';
 
    return 0;
}