[ 백준 17281 ] 야구 (C++)

백준의 야구(17281) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 본인 처럼 야구를 잘 모르는 사람이거나 혹은 예제입력들의 답이 왜 저렇게 나오는지 모르겠는 사람들을 위해서

   본인의 얕은 지식으로 야구에 대해서 까지는 아니고 야구를 이 문제와 함께 설명해보고자 한다.

 ( 야구의 룰을 잘 아시거나, 예제 입력과 예제 출력의 결과가 이해가 되시는 분들은 2)번 으로 넘어가셔서 구체적인

   풀이 부터 보셔도 무방합니다. )

   먼저, 총 9명으로 이루어진 팀이 총 N이닝 동안 게임을 진행한다. 절대로 N이닝 동안, 9명의 선수가 모두 공격을 할 수

   있는 것이 아니고 한 이닝에서 Out이 3개가 되면 이닝이 종료된다.

   예를 들어서 총 2이닝 동안 경기를 진행하는데, 1~9번 타자 모두 '아웃'밖에 칠 수 없는 경우에는

   6명만 공격을 하고 게임이 끝날 것이다. 왜냐하면 1,2,3번 타자가 아웃을 침으로써 3아웃으로 1이닝이 종료될 것이고,

   2 이닝에서는 4,5,6번 타자가 아웃을 침으로써 3아웃으로 2이닝이 종료될 것이다. 경기를 총 2이닝 동안 진행되니까

   점수가 0점으로 끝나게 된다. 뭐 이런식으로 경기가 진행된다.

   그렇다면 예제입력을 한번 봐보도록 하자. 예제 입력은 9개의 숫자들이 나열되어 있는 식으로 주어진다.

   예제입력1을 보게되면

   4 0 0 0 0 0 0 0 0

   4 0 0 0 0 0 0 0 0

   이런식으로 주어져 있는데, 첫째줄은 '1이닝'을 , 둘째줄은 '2이닝'을 의미한다.

   그리고 9개의 숫자는 '9명의 선수들의 능력치(?)' 라고 생각하면 좋을 것 같다.

   제일 앞에 '4'가 의미하는 것은, 1번 선수가 1이닝에 출전하게 되면 '4(홈런)'을 칠 수 있습니다. 라는 것을 의미한다.

   또한, 2 ~ 9번 선수가 1이닝에 출전하게 되면 '0(아웃)'을 칠 수 있습니다. 라는 것을 의미한다.

   그럼 분명히, 1번선수가 각 이닝에서 홈런을 한번씩 치게 되면 총 2점을 얻을 수 있지 않나? 근데 왜 답은 1이지?

   라고 생각할 수 있는데, 아까도 말했듯이 한 이닝은 3아웃이 되면 끝나게 된다.

   지금부터, 1번~9번 선수가 순서대로 출전한다고 가정하고, 문제의 조건을 빼고 설명해 보겠다.(1번 선수가 4번 타자로

   출전한다는 조건을 제외하고) 1번선수가 1이닝에 1번타자로 출전했으므로 1점이 날 것이다. 홈런을 칠 것이기 때문이다.

   그리고 2 ~ 4번타자의 연속된 아웃으로 인해 3Out으로 1이닝이 종료되게 된다. 그렇다면 2이닝은 누구부터 시작할까?

   5번 타자부터 시작하게 된다. 2이닝이 시작하자마자 5~7번 선수들의 연속된 3Out으로 2이닝이 종료되게 된다.

   즉, 1번 타자는 2이닝에 출전해서 홈런을 칠 수 있음에도 칠 수가 없게된다. 따라서 점수가 1점 밖에 날 수 없다.

   그렇다면 예제입력 2번을 한번 봐보도록 하자.

   어떻게 하면 4점이 날 수 있을까? 5~7번 선수가 1~3번 타자로 출전하고, 1번 선수가 4번 타자로 출전하게 되면 ??

   그렇게 되면 1~3번 타자의 안타들로 인해서, 1루 2루 3루에 사람이 한명씩 가있는 꼴이 될 것이고, 4번 타자의 홈런에

   의해서 1루, 2루, 3루 + 4번타자 에 있는 총 4명이 점수를 낼 수 있게 되므로 총 4점을 얻을 수 있게 된다.

   이런식으로 진행되어 진다.

2) 본격적인 구현에 들어가보자. 본인은 가장 먼저 '순열 구현' 을 하였다. 이 문제에서 해야할 일은 각 선수들의 타순을

   정해주고, 최대 점수를 낼 수 있을 때의 점수를 구하는 것이 문제이다.

   즉, 9명의 선수들을 순서대로 세워보면서 각각의 경우에 대해서 점수를 계산해주면 된다.

   아직 순열을 구현하는 법을 잘 모른다면 아래의 글을 읽고 오도록 하자 !

   [ 순열 구현하기 바로가기(Click) ]

   그런데 왜 조합이 아니고 순열일까??? 바로 '순서에 영향을 미치기 때문' 이다. 2번선수가 1번 타자로 출전하고,

   3번선수가 2번 타자로 출전하는 것과, 3번선수가 1번 타자로 출전하고, 2번선수가 2번 타자로 출전하는 것은 결과가

   달라질 수 있기 때문에 순서에 영향을 미친다고 볼 수 있다. 따라서 순열을 구현한 것이다.

   단 ! 문제에서 주어진 조건을 절대 빼먹으면 안된다. 바로 "4번 타자는 1번선수가 출전한다" 라는 조건이다.

   본인은, 순열을 구현할 때, 2개의 배열을 핵심적으로 사용해 주었는데

   첫번째는 Select[] 배열이다. 일반 순열과 동일하게, 이미 뽑았는지를 판단하기 위한 배열로써

   Select[a] = true의 의미는 "a번 타자를 이미 골랐습니다." 를 의미한다.

   두번째는 Order[] 배열이다. 이는, 순서를 저장해주는 배열인데, Order[a] = b의 의미는 "a번 타자는 b번 선수입니다."

   를 의미한다.

   따라서 본인은 문제의 조건을 만족시키기 위해서 순열을 구현하기 전에 미리

   Select[4] = true , Order[4] = 1 로 설정해준 뒤, 순열을 구현하였다.

   이는, "4번 타자는 이미 골랐고, 4번 타자는 1번 선수입니다" 를 의미하게 된다.

3) 지금까지 순열을 구현하였다면 이제부터는 실제로 경기를 진행하면 된다. 이 후에는, 홈, 1루, 2루, 3루를 표현하는

   4칸짜리 배열을 하나 만들어서, 현재 사람이 있는지 없는지를 판단해 가면서 하나하나 값을 바꿔주는 식으로 구현해 보았다.

   사실 이부분은 말로 설명하기 힘들어서 코드에 있는 주석으로 대체하겠다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 50 + 1
#define PLAYER_NUM 10
using namespace std;
 
int N, Answer;
int Order[PLAYER_NUM];      // 타순을 저장하기 위한 배열
int Game[MAX][PLAYER_NUM];  // 각 이닝에서의 선수들의 능력치 저장
bool Select[PLAYER_NUM];    // 이미 뽑은 타순인지 판단하기 위한 배열
vector<int> V;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j < PLAYER_NUM; j++)
        {
            cin >> Game[i][j];
            /* Game[i][j]의 의미
               Game[1][2] = 3 이라는 예로 설명을 하면
               "1이닝에서 2번 선수는 3(3루타)를 칩니다." 를 의미한다.
            */
        }
    }
}
 
void Play_The_Game()
{
    /* 실제로 게임을 진행해보기 위한 함수 */
    int Score = 0;
    int Start_Player = 1;
    int Base_State[4];    
    /* Base[4]의 의미.
       Base[0] = 홈, Base[1] = 1루, Base[2] = 2루, Base[3] = 3루를 의미한다.
       Base[x] = 0의 의미는 "현재 x루 에는 사람이 없습니다."를 의미하고
       Base[x] = 1의 의미는 "현재 x루 에는 사람이 있습니다."를 의미한다.
       즉, 누군가가 안타, 1루타, 2루타, 3루타 등을 치게 될 경우
       각각의 상황에 맞게 Base[]의 상태를 변경해준다.
    */
 
    for (int i = 1; i <= N; i++)  // 총 N이닝 동안 진행
    {
        int Out_Cnt = 0;
        bool Next_Ining = false;
        memset(Base_State, 0, sizeof(Base_State));
 
        while (1)
        {
            for (int j = Start_Player; j < PLAYER_NUM; j++)
            {
            // 순서가 정해진 대로 선수들이 타석으로 출전.
                int Player = Game[i][Order[j]];
 
                if (Player == 0) Out_Cnt++;       // 아웃을 치게되면 Out_Cnt 증가
                else if (Player == 1)             // 안타를 치게되면
                {
                    for (int F = 3; F >= 1; F--)  // 각 루에 있던 선수들이 한 칸씩 전진하게 된다.
                    {
                        if (Base_State[F] == 1)   
                        {
                            if (F == 3)           // 3루에 선수가 있었다면
                            {
                                Base_State[F] = 0;// 홈으로 들어가게되고
                                Score++;          // 점수가 1점 ++
                            }
                            else                   
                            {
                                Base_State[F + 1] = 1; // 3루가 아닌 선수들은 1루씩 전진
                                Base_State[F] = 0;     
                            }
                        }
                    }
                    Base_State[1] = 1;
                }
                else if (Player == 2)            // 2루타도 마찬가지 원리 !
                {
                    for (int F = 3; F >= 1; F--)
                    {
                        if (Base_State[F] == 1)
                        {
                            if (F == 3 || F == 2)
                            {
                                Base_State[F] = 0;
                                Score++;
                            }
                            else
                            {
                                Base_State[F + 2] = 1;
                                Base_State[F] = 0;
                            }
                        }
                    }
                    Base_State[2] = 1;
                }
                else if (Player == 3)            // 3루타도 마찬가지 원리 ! 
                {
                    for (int S = 3; S >= 1; S--)
                    {
                        if (Base_State[S] == 1)
                        {
                            Base_State[S] = 0;
                            Score++;
                        }
                    }
                    Base_State[3] = 1;
                }
                else                             // 홈런일 경우
                {
                    for (int F = 1; F <= 3; F++) 
                    {
                        if (Base_State[F] == 1)
                        {
                            Base_State[F] = 0;
                            Score++;             // 어떤 루에 있던 간에 무조건 홈으로 들어갈 수
                                                 // 있으므로 점수++
                        }
                    }
                    Score++;
                }
 
                if (Out_Cnt == 3)                 // 3Out이 되면 그 다음 이닝으로 넘어간다.
                {
                    Start_Player = j + 1;
                    if (Start_Player == PLAYER_NUM) Start_Player = 1;
 
                    Next_Ining = true;
                    break;
                }
            }
            if (Next_Ining == true) break;
            Start_Player = 1;
        }
    }
 
    Answer = Bigger(Answer, Score);
}
 
void DFS(int Cnt)
{
    /* 순열을 구현하기 위한 DFS 함수 부분 */
    if (Cnt == PLAYER_NUM)
    {
        Play_The_Game();
        return;
    }
 
    for (int i = 1; i < PLAYER_NUM; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Order[i] = Cnt;
        DFS(Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    /* 문제의 제약조건. 4번 타자로는 무조건 1번 선수가 출전한다. */
    Select[4] = true;    // 4번 타자를 이미 골랐습니다.
    Order[4] = 1;        // 4번 타자는 1번 입니다.
    DFS(2);              // 순열 구현을 위한 재귀호출
 
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}