[BOJ/C++] 17281 ⚾

시간 복잡도

• 9명의 선수들의 타자 순서에 대한 순열의 경우의 수는 $9!$ 입니다.
• 최대 50이닝 이므로 시간 복잡도는 $O(9! * n)$ 이므로 충분합니다.

문제 접근법

• 9명의 선수들에 대한 모든 순서 조합에 대하여 이닝을 진행합니다.
• 3명이 아웃되었다면 다음 이닝을 진행합니다.
• 각 타자의 결과에 따라 베이스의 주자들을 진루합니다.
• next_permutation을 이용해 타자의 모든 순열을 구할 수 있습니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;


static int N;
static int avg[50][9] = {};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 9; j++)
            cin >> avg[i][j];
    }

    // 타자 순서의 조합 배열
    vector<int> p = { 1, 2, 3, 4 ,5 ,6 ,7, 8 };
    int answer = 0;

    do
    {
        // 타자 순서 배열
        vector<int> seq = p;
        seq.insert(seq.begin() + 3, 0);     // 1번 선수를 4번 타자로 설정

        int score = 0, idx = 0;

        for (int i = 0; i < N; i++)
        {
            bool base[3] = {};
            int out = 0;

            while (out < 3)
            {
                int hit = avg[i][seq[idx]];

                if (hit == 0)
                    out++;
                else if(hit==4)
                {
                    score++;
	                for(int k=0; k<3; k++)
	                {
                        if (base[k])
                        {
                            score++;
                            base[k] = false;
                        }
	                }
                }
                else
                {
	                for(int k=2; k>=0; k--)
	                {
		                if(base[k])
		                {
                            int next = k + hit;
                            if(next>2)
                                score++;
                            else
                                base[next] = true;

                            base[k] = false;
		                }
	                }
                    base[hit - 1] = true;
                }
                idx = (idx + 1) % 9;
            }

        }
        answer = max(answer, score);

    } while (next_permutation(p.begin(), p.end()));

    cout << answer;

    return 0;
}