백준 17281번: ⚾
거진 일주일 만에 쓰는 포스트-

1) 문제 분석

  일단 모든 순열에 대해 경기 점수를 따져보면 될 것 같은 문제였는데 그렇게하면 실행 시간이 꽤 걸릴 것 같아서 더 효율적인 방법이 없나 한참을 고민하다가 결국 순열 구하는 재귀함수를 이용해서 해결한 문제이다. 혹시나해서 다른 사람들 코드를 살펴봤는데 다른 방법은 보지 못했다. 하지만 코드를 보던 중 c++ 표준 라이브러리에서 next_permutation 이라는 아주 편리한 함수를 제공한다는 것을 알게되었다.

2) std::next_permutation

bool next_permutation (BidirectionalIterator first,BidirectionalIterator last);
bool next_permutation (BidirectionalIterator first,BidirectionalIterator last, Compare comp);

  first가 가리키는 원소부터 last의 이전 iterator가 가리키는 원소까지[first,last) 의 순열을 차례로 만들어주는 함수이다.
이 때, 컨테이너 자체의 내용물이 변한다. 즉, 이 함수를 실행할 때 마다, [first,last)가 가리키는 원소들을 재배치해서 순열을 만들어주는 것이다.
눈여겨 볼 점은, 여러가지 순열들 사이에 순서가 존재해서 이 함수를 호출할 때 마다 그 순서대로 순열을 만들어준다는 것이다. 순열들의 정렬의 방법은 c++ 레퍼런스에 의하면 lexicographical이라고 한다. 대충 해석해 보자면, 두 비교 대상에 대해서 처음 원소부터 차례로 같은 위치에 있는 원소들끼리 비교를 해주고 서로 다른 원소들이 등장하면 그 원소들의 비교값이 비교 결과라는 것이다. 말이 좀 복잡하지만 c에서 strcmp가 동작하는 원리와 같다. hat과 had라는 단어가 있을 때 첫 글자부터 비교를 해주다가 세 번째 글자인 t와 d가 다를 때 d<t이므로 had<hat이 결과가 된다.
  next_permutation도 이런 방식으로 순열들을 정렬하는데, next_permutation에 세 번째 인자로 비교 함수를 전달해주면 두 원소의 비교 방식을 바꿔줄 수도 있는 것 같다(sort 함수에서처럼). 함수의 반환값은, 더 가능한 순열이 있으면 true 그렇지 않으면 false이다.

3) 코드

#include <iostream>
#include <vector>

using namespace std;

int inning[50][10];   //각 이닝에서의 각 선수의 결과
int N;                //이닝 횟수
bool in[10];          //순열에 포함되어있는지 아닌지
int max_points = -1;  //얻을 수 있는 최대 점수
vector<int> players;  //선수 순열

/**
 * 재귀적으로 선수들의 순열을 찾아서 해당 타순일 때의 경기 점수를 구함
 */
void solve(){
    int len = players.size();
    //순열이 완성됨
    if(len==9){
        int out = 0; //아웃 횟수
        int nth = 0; //n+1번째 이닝
        int base[4] = {0,0,0,0};  //루, base[3]이 홈
        int p = 0;   //타자 순서

        //모든 이닝이 끝날 때 까지
        while(nth<N){
            //(nth+1)번 째 이닝에서 players[p]번 타자의 결과
            switch(inning[nth][players[p]]){
                case 0: //아웃
                    out++;
                    break;
                case 1: //안타
                    base[3]+=base[2]; base[2]=base[1];
                    base[1]=base[0]; base[0]=1;
                    break;
                case 2: //2루타
                    base[3]+=(base[2]+base[1]);
                    base[2]=base[0];
                    base[1]=1; base[0]=0;
                    break;
                case 3: //3루타
                    base[3]+=(base[2]+base[1]+base[0]);
                    base[2]=1; base[1]=base[0]=0;
                    break;
                case 4:  //홈런
                    base[3]+=(base[2]+base[1]+base[0]+1);
                    base[2]=base[1]=base[0]=0;
                    break;
            }
            p = (p+1)%9;
            //삼진
            if(out==3){
                out=0;
                base[2]=base[1]=base[0]=0;
                //다음 이닝
                nth++;
            }
        }
        //최댓값 구함
        if(max_points<base[3])
            max_points = base[3];
    }
    //1번 주자는 4번으로 고정된다 
    else if(len==3){
        players.push_back(1);
        solve();
        players.pop_back();
    }
    else{
        for(int i=2; i<=9; i++){
            if(in[i]) continue;
            in[i] = true;
            players.push_back(i);
            solve();
            in[i] = false;
            players.pop_back();
        }
    }
}

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

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

    solve();
    cout<<max_points;
}