[백준] 17281 ⚾

 

문제를 이해하는데 오래걸렸던 문제다

 

야구를 하는데 총 N 이닝동안 진행을 하고

나는 선수들이 어떻게 공을 치는지 알고있다

 

내가 할 일은 순서만 정해주는 것이다!

 

여기서 조건은 1번타자는 무조건 4번째에 쳐야하고

이닝이 끝났을 때 이전 이닝에 마지막으로 친 타자 다음 타자부터 시작하고

아웃이 3번 된다면 해당 이닝이 끝난다는것!

 

구현자체는 어렵지 않은데 엄청 헷갈렸다

특히 점수를 매기는 과정에서 나는 배열을 만들어서 구현했는데

이 부분에서 내 앞의 3타자에게 점수를 줄 때는 답이안나왔고

내 뒤에 3타자로부터 점수를 받을 때는 답이 나왔다..!

구현 실수같은데 왜 그런지는 못 찾았다

 

어쨌든 문제를 풀어본다면!

 

먼저 순서를 정해야 하므로 next_permutation을 쓴다!

근데 이 때 order[0] = 3으로 미리 정해두고 order[1]~order[8]만 순열을 돌린다

1번타자가 4번타자로 정해져있기 때문에!!

 

그리고 norder를 통해 현재 순서를 다시 배열에 넣어주고

n이닝까지 돌려보면 된다

 

zero가 3이 될때까지 prev~pos까지 구간을 정해 배열에 넣어준다

그리고 점수 내는 부분을 생각해보면 나는 내 뒤에 3명에게 영향을 받는다

그래서 그 3명이 앞으로 가는만큼 나도 가면 된다!

 

그 부분을 처리해주는데 이 때 내가 아웃이면 skip~~!

 

다 처리하고 마지막으로 점수 낸 사람의 최대를 구해주면 된다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n,ans;
int order[9] = {3,0,1,2,4,5,6,7,8};
int norder[9];
int score[10][55];
int arr[1515];
 
int main(){
    scanf(" %d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<9;j++){
            scanf(" %d",&score[j][i]);
        }
    }
 
    do{
        for(int i=0;i<9;i++) norder[order[i]] =i;
        int cnt=0,pos=0;
        for(int i=0;i<n;i++){
            int zero=0;
            int prev=pos;
            while(zero != 3){
                int num = score[norder[pos%9]][i];
                if(num==0) zero+=1;
                arr[pos++]=num;
            }
            for(int j=prev;j<pos;j++){
                if(!arr[j]) continue;
                for(int k=j+1;k<=j+3,k<pos;k++) arr[j]+=arr[k];
            }
        }
        for(int j=0;j<pos;j++) if(arr[j]>=4) cnt+=1;
        ans = max(ans,cnt);
    }while(next_permutation(order+1,order+9));
    printf("%d\n",ans);
}