[백준] 17281번 : ⚾

문제

 

---

풀이

 

각 선수가 몇 번 타자가 될 지는 next_permutation으로 구하면 된다.

다만, 1번 선수가 4번 타자인건 고정이니 2~9번 선수들에 대해서만 순열을 돌리고 4번 타자가 된 선수와 1번 선수를 바꾸면 되겠다.

 

점수나 다음 타자는 이닝이 바뀌어도 누적되는 결과니까 전역변수로 처리하면 된다.

그리고 1, 2, 3루 각 플레이트에 선수가 있는지 없는지를 저장해야 하는데...나는 비트 마스킹을 썼다.

 

1110 : 1, 2, 3루에 주자 존재

0100 : 2루에 주자 존재

1010 : 1, 3루에 주자 존재

 

가장 오른쪽 비트는 이번에 나선 타자를 위해 남겨뒀다.

아무튼 이런식으로 하면 주자 이동도 3루타 일때 (1011)<<3 = 1000 이런식으로 간단하게 처리할 수 있다.

엄밀히 말하면 1011000이 되겠지만 그렇게 되지 않도록 내가 처리할 것이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int score, player;
vector<int> entry = {0, 1, 2, 3, 4, 5, 6, 7, 8}; //선수 순서
vector<vector<int>> board;

void running(int &run, int num) {
    run |= (1 << 0); //0번 플레이트에 선수 표시
    for (int i = (4 - num); i < 4; i++) {
        if (run & (1 << i)) { //홈에 도착하게 될 주자
            run &= ~(1 << i); //0으로 변경
            score++; //점수 증가
        }
    }
    run = run << num; //주자 이동
}

void playGame(int idx) {
    int out = 0, run = 0; //아웃카운트, 진루 상태
    while (out != 3) { //3아웃 미만일 동안
        int hit = board[idx][entry[player]]; //이번 주자의 결과
        if (!hit) //아웃
            out++;
        else //존재하는 모든 주자 진루
            running(run, hit); 
        player = (player + 1) % 9; //다음 선수
    }
}

int main() {
    int N, result = 0;

    cin >> N;
    board.assign(N, vector<int>(9));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 9; j++)
            cin >> board[i][j];
    }
    do {
        swap(entry[0], entry[3]); //1번 선수 4번 타자 되도록
        score = player = 0; //초기화
        for (int i = 0; i < N; i++) //모든 이닝 플레이
            playGame(i);
        result = max(result, score); //최댓값 갱신
        swap(entry[3], entry[0]); //원래대로 복구
    } while (next_permutation(entry.begin() + 1, entry.end()));
    cout << result;
}

전체 소스코드다.

 

    do {
        swap(entry[0], entry[3]); //1번 선수 4번 타자 되도록
        score = player = 0; //초기화
        for (int i = 0; i < N; i++) //모든 이닝 플레이
            playGame(i);
        result = max(result, score); //최댓값 갱신
        swap(entry[3], entry[0]); //원래대로 복구
    } while (next_permutation(entry.begin() + 1, entry.end()));

가능한 모든 엔트리에 대해 시뮬레이션을 돌려본다.

 

        score = player = 0; //초기화
        for (int i = 0; i < N; i++) //모든 이닝 플레이
            playGame(i);

각 엔트리마다 score와 player를 0으로 초기화 하고, 모든 이닝을 플레이해본다.

 

void playGame(int idx) {
    int out = 0, run = 0; //아웃카운트, 진루 상태
    while (out != 3) { //3아웃 미만일 동안
        int hit = board[idx][entry[player]]; //이번 주자의 결과
        if (!hit) //아웃
            out++;
        else //존재하는 모든 주자 진루
            running(run, hit);
        player = (player + 1) % 9; //다음 선수
    }
}

각 이닝은 아웃카운트가 3이 되면 끝난다.

 

        int hit = board[idx][entry[player]]; //이번 주자의 결과

이번 타자의 결과를 hit에 저장한다. 0~4까지의 수가 저장된다.

 

        if (!hit) //아웃
            out++;
        else //존재하는 모든 주자 진루
            running(run, hit);

0이면 아웃카운트를 늘려주고, 아니라면 진루 처리 한다.

 

void running(int &run, int num) {
    run |= (1 << 0); //0번 플레이트에 선수 표시
    for (int i = (4 - num); i < 4; i++) {
        if (run & (1 << i)) { //홈에 도착하게 될 주자
            run &= ~(1 << i); //0으로 변경
            score++; //점수 증가
        }
    }
    run = run << num; //주자 이동
}

먼저 run |= (1<<0)으로 타자의 진루를 표시한다.

 

    for (int i = (4 - num); i < 4; i++) {
        if (run & (1 << i)) { //홈에 도착하게 될 주자
            run &= ~(1 << i); //0으로 변경
            score++; //점수 증가
        }
    }

홈에 도착하게 될 주자가 몇명인지 세본다.

아까 1101에서 3루타를 쳐서 110 1000이 됐을때, 삐져나온 110에 대해 1의 개수를 세는 것이다.

개수를 세면서 0으로 변경해서 4비트를 유지한다.

 

    run = run << num; //주자 이동

그럼 주자 이동은 한줄로 처리할 수 있다.

 

        player = (player + 1) % 9; //다음 선수

while문을 돌면서 player의 인덱스를 하나씩 옮겨주는데 9번 타자 -> 1번 타자일 수도 있으니 모듈러로 처리한다.

 

        result = max(result, score); //최댓값 갱신

이렇게 최댓값 갱신하고 출력하면 된다.