[Algorithm] BOJ 17281 ⚾

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

17281 ⚾

---

문제

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.

두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.

공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.

타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.

• 안타: 타자와 모든 주자가 한 루씩 진루한다.
• 2루타: 타자와 모든 주자가 두 루씩 진루한다.
• 3루타: 타자와 모든 주자가 세 루씩 진루한다.
• 홈런: 타자와 모든 주자가 홈까지 진루한다.
• 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.

한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.

입력

첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.

• 안타: 1
• 2루타: 2
• 3루타: 3
• 홈런: 4
• 아웃: 0

각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.

출력

아인타팀이 얻을 수 있는 최대 점수를 출력한다.

예제

---

풀이

---

생각

• 이 문제는 은근 정의들이 헷갈린다. 야구에 대해 아주 간단한 지식이라도 있다면 여러 문제요소들은 다 이해될 것이다. 하지만 19번 선수들이 있으면 각 선수마다 타자 순서를 19번 부여한다는 것이 은근 헷갈린다.
  • 각 요소마다의 제대로 된 정의를 해놔야 헷갈리지 않을 문제.
• 1~9번 선수가 존재하는데, 각 이닝에서의 결과가 인풋으로 주어진다. 이 경우의 수로 최종 최대 득점을 구하는 것.
  • 대충 봐도 알겠지만, 결국은 모든 선수의 순서 경우의 수를 계산하고 그 때의 득점을 계산해 최대 득점을 구해야한다.
  • 백트랙킹 + 완전탐색
• 1번 선수는 무조건 4번 타자 --> 4번 타자 순서에 무조건 1번 선수를 넣어놀까?
  • 내가 머리가 안좋은가, 백트랙킹이 초보라 그런가 이걸 어떻게 구해야할지 모르겠더라... 앞 수가 고정되거나, 제대로 경우의 수를 탐색하지 못한다던가.
  • 그래서 그냥 4번 타자가 첫 번째 선수인 경우에만 게임을 시작하게 수행했다.
  • 근데 이러면 탐색 시간 버리는거 아닌가? 다 탐색해놓고 마지막 가서 4번 타자가 첫 번째 선수가 아니니깐 안돼! 이런느낌인데. 그냥 4번 타자 고를 때 첫 번째 선수만 고르도록 수행하면 안되나? (다시 해봐야지..)
• 아무튼, 선수 타자 순서를 다 설정하고 나면 게임을 시작하면 된다.
  • 게임 구현은 쉽다. 일반 야구처럼 1/2/3루를 정해두고 안타/2루타/3루타/홈런/아웃마다 다른 행동을 해주면 된다.
  • switch를 사용해 간결하게 짰다.

방법

• 일단 selecting 함수를 통해 선수를 순서를 정하는 모든 경우의 수를 구한다.
  • fix: 현재 타자순서
  • i: 선수번호
  • player[fix] = i: 타자 순서 fix번에 선수번호 i 선수를 할당.
• for loop
  • already를 통해 벌써 선택되어 있는가를 확인
  • 선택되어 있지 않다면, 현재 타자 순서에 선수를 선택하고, already도 설정한다. 그리고 재귀로 다음 순서 선수를 설정하도록 수행.
  • 다시 돌아오게 되면 다음 순번으로 정하는 경우도 할 수 있도록 already를 풀어준다.
• 만약 선수 9명에 대해 순서를 다 정해준 경우에서 첫 번째 선수가 4번째 타자인 경우엔 게임을 시작한다.
  • 게임의 경우는 명시된 데로 코드를 짜면 된다.
  • 타자 순서가 다음 이닝에도 연속적으로 수행되므로 이닝 밖에서 변수를 선언하고, 다음 선수로 넘어갈 때 9를 넘어갈 것을 대비해서 % 연산으로 계속 반복하도록 만들어준다.
• 게임 결과가 현재 최대값보다 큰 경우, 업데이트 해준다.

유의

• '생각'부분에서도 말했듯이 '선수번호'와 '타자순서'에 대한 정의를 명확히 정해놓고 수행해야한다.
  • 안그럼 player 변수 안에 들어가는 것은 무엇이고, 인덱스는 무엇인지 계속 헷갈리게 된다.
• 게임 코드를 짤 때, 이닝이 진행되도 타자 순서는 계속 연속적이기 때문에 이닝 수행하는 부분보다 밖에서 타자순서에 대한 변수를 정의해줘야 한다는 것을 생각해야한다.

---

코드

---

#include <iostream>
#include <algorithm>
#define bb ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int n, game[51][9], player[9];
bool already[9];
int maxres;

int start() {
    int res = 0, j = 0;
    for (int i = 0; i < n; ++i) {
        int cnt = 0, g[4] = { 0, };
        while (true) {
            if (cnt >= 3) {
                res += g[3];
                break;
            }
            switch (game[i][player[j]]) {
            case 0:
                cnt++;
                break;
            case 1:
                g[3] += g[2];
                g[2] = g[1];
                g[1] = g[0];
                g[0] = 1;
                break;
            case 2:
                g[3] += (g[2] + g[1]);
                g[2] = g[0];
                g[1] = 1;
                g[0] = 0;
                break;
            case 3:
                g[3] += (g[2] + g[1] + g[0]);
                g[2] = 1;
                g[1] = g[0] = 0;
                break;
            case 4:
                g[3] += (g[2] + g[1] + g[0] + 1);
                g[2] = g[1] = g[0] = 0;
                break;
            }
            j = (j + 1) % 9;
        }

    }
    return res;
}

void selecting(int fix) {
    if (fix == 9 && player[3] == 0) {
        maxres = max(maxres, start());
        return;
    }

    for (int i = 0; i < 9; ++i) {
        if (already[i]) continue;
        player[fix] = i;
        already[i] = true;
        selecting(fix + 1);
        already[i] = false;
    }
}

int main() {
    bb;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 9; ++j)
            cin >> game[i][j];

    selecting(0);

    cout << maxres << '\n';

    return 0;
}

---

느낀점

• 백트랙킹만 잘 구축했다면 어렵지 않았던 문제.
• 앞서 말했듯이 첫 번째 선수를 4번 타자로 설정을 하는 부분에서 좀 애먹었다.
  • 좀 더 효율적으로 수행하고 싶은데, 이걸 어디서 선언해줘야할까.
  • 잘 때되서 짜서 그런가.... 맘이 좀 급하기도 했다... (변명)

---

참조

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