[BOJ] 17281 ⚾

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

17281번: ⚾

처음에는 그냥 타자의 순서를 정하는 게 메인인 문제인 줄 알았는데, 그건 기본이고 야구의 득점 시스템을 구현하는 것이 메인이었다.

타자 순서는 그냥 재귀와 반복문을 통해서 구현하였다. 야구의 득점 시스템은 크기가 3인 base라는 bool 순열을 이용하여 base에 사람이 있는지 없는지를 나타내 구현하였다.

 

안타를 쳤을 경우를 구현하는 것이 어려웠다. 수학적으로 간단히 구현이 가능할 줄 알았는데 경우의 수가 너무 많아 안되었고 일일이 안타만큼 base의 선수들을 옮겨 구현하였다.

 

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> player[9]; // 각 이닝에 선수가 낼 수 있는 점수를 저장

int N,ans=0;
int seq[9]; // 현재 야구 ratation을 저장
bool check[9];
bool base[3]; // 각각의 base에 사람이 있는지 없는지를 나타냄

void input(){
    int x;
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<9;j++){
            cin>>x;
            player[j].push_back(x);
        }
    }
}

void init() {
    check[0]=true;
    seq[3]=0;
}

int cal(){
    int out_count,index=0,player_score;
    int sum=0;
    for(int i=0;i<N;i++){
        out_count=0;
        fill(&base[0],&base[3],false); // 이닝이 시작할 때 base에 주자가 있으면 안된다.
        while(out_count!=3){
            player_score=player[seq[index%9]][i];
            index++;
            if(player_score==0){
                out_count++;
                continue;
            }
            
            if(player_score==4){ // 홈런을 쳤을 경우 base에 있는 주자 + 1(홈에 있는 주자) 만큼 득점한다.
                for(int i=0;i<3;i++)
                    if(base[i]){
                        sum++;
                        base[i]=false;
                    }
                sum++;
                continue;
            }
            
            //안타를 쳤을 경우 구현
            for(int i=2;i>=0;i--){
                if(base[i]){
                    if(i+player_score>2) sum++;
                    else base[i+player_score]=true;
                    base[i]=false;
                }
            }
            base[player_score-1]=true;
        }
    }
    
    return sum;
}

void solution(int n) {
    if(n==3){
        solution(n+1);
    }else if(n==9){
        ans=max(ans,cal());
    }else{
        for(int i=1;i<9;i++){
            if(!check[i]){
                check[i]=true;
                seq[n]=i;
                solution(n+1);
                check[i]=false;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    init();
    solution(0);
    cout<<ans;
    return 0;
}