17281. ⚾

문제 링크

17281번: ⚾

풀이

이닝에서 얻을 수 있는 최대 결과가 딱히 공식으로 있지도 않고, 있더라도 몹시 복잡할 것 같다. 이닝 수가 최대 50밖에 되지 않고, 가능한 타순의 가짓수도 \(8!=40320\)이니(4번째 타순은 1번 타자로 고정이므로), 이 정도면 브루트 포스(brute force)로 풀어볼 만하다.

일단 타순의 경우 4번째 타순을 제외한 나머지 타순을 next_permutation 함수로 전부 돌려볼 수 있을 것이다. 반복문에서 각 타자의 이닝 결과를 얻는 데 조금 귀찮겠지만, 어려울 건 없다.

그리고 이닝 결과에 따른 진루와 점수 획득을 구현하는 게 또다른 핵심인데, 필자는 처음 풀 때 큐를 이용하여 구현하였다. 그런데 큐를 쓰니 실행 속도가 매우 느리게 찍히는 것이 아닌가. 그래서 다 풀고 다른 사람의 풀이를 참고했는데, 다들 배열로 진루를 구현하고 있었다. 그래서 동일하게 배열로 다시 구현한 결과, 실행 속도가 2배 이상으로 상당히 빨라졌다.

그래서 진루를 어떻게 구현하는지는 간단하다. 배열 원소 하나하나를 야구장의 각 루로 정의하고, 선수가 루에 있으면 true, 없으면 false로 한다. 그리고 안타면 각 원소값을 한 칸씩 이동, 2루타면 두 칸씩 이동하는 식으로 구현하면 된다. 만약 선수가 루를 한 바퀴 돌았을 때(true인 원소가 이동해서 배열 범위를 벗어나려 할 때)는 1점을 추가하도록 한다.

시간 복잡도

최악의 경우(worst case)는 9번째 타자의 이닝 결과가 아웃(0)일 경우이며, 이때 한 이닝 당 같은 타순을 3바퀴 돌게 된다. 이것이 최대 50이닝 존재하여 야구 한 판을 이루고, 이러한 판이 타자 순번의 가짓수(\(8!=40320\))만큼 존재한다. 이를 종합하면 시간 복잡도는 \(O(8!\times 50\times 3)=O(6048000)\)이다.

소스코드

#include <iostream>
#include <algorithm>
#define NUM    9
using namespace std;

int N, ans;
int inning[50][NUM];
int order[] = {1, 2, 3, 4, 5, 6, 7, 8};

// 정해진 타순에 따라 야구하는 함수
int baseball() {
    int id = 0, score = 0;
    
    // 이닝 횟수만큼 반복
    for(int i = 0; i < N; i++) {
        int out = 0;
        bool base[4] = {false, false, false, false};
        
        // 한 이닝을 3아웃이 될 때까지 반복
        while(out < 3) {
            int result;
            id %= NUM;
            if(id < 3) result = inning[i][order[id]];
            else if(id == 3) result = inning[i][0];
            else result = inning[i][order[id - 1]];
            
            if(result == 0) out++;
            else {
                base[0] = true;
                for(int j = 0; j < result; j++) {
                    if(base[3]) score++;
                    for(int k = 2; k >= 0; k--) {
                        base[k + 1] = base[k];
                    }
                    base[0] = false;
                }
            }
            
            id++;
        }
    }
    
    return score;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < NUM; j++) {
            cin >> inning[i][j];
        }
    }
    
    do {
        ans = max(ans, baseball());
    } while(next_permutation(order, order + NUM - 1));
    
    cout << ans;
    return 0;
}