BJ17281 ⚾

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

안녕

풀이

알고리즘

BruteForce + Simulation

시간복잡도

50(이닝수) * 27(최악의 simulation : 3 아웃되는 동안 모든 타자가 타석에 서는 경우) * 8팩토리얼(타자 순서 정하는 모든 경우의 수) = 5500만 정도

함수

getResult : 타자 순서를 정하고 기저조건에서 점수를 얻어와 최대 점수를 반환하는 함수

playGame : 기저조건이 되었을 때 문제의 조건에 맞게 이닝별로 점수를 계산해서 반환하는 함수

movePlayer : 이닝별로 playGame에서 Simulation을 할 때 아웃이 아닌 경우에 1~3루, 홈 에 선수들을 옮기는 함수

코드

//! 2020.02.20 ~ 2020.02.21
// TODO BJ17281_Baseball
#include<cstdio>
using namespace std;
const int MAX = 55;
const int NP = 9;
int inData[MAX][NP];
int T;
bool check[NP];
int orderP[NP];
int Nru[4];

void movePlayer(int hits) {
    for (int i = 2; i >= 0 ; i--) {
        if (Nru[i] != 0) {
            int next = i + hits;
            if (next >= 3) next = 3;
            Nru[i]--;
            Nru[next]++;
        }
    }
    Nru[hits - 1]++;
}

int playGame() {
    int thisRet = 0;
    int cur = 0;
    for (int t = 0; t < T; t++) {
        int cnt = 0;
        while (cnt < 3) {
            int player = orderP[cur % NP];
            if (inData[t][player] == 0) cnt++;
            else movePlayer(inData[t][player]);
            cur++;
        }
        thisRet += Nru[3];
        for (int i = 0; i < 4; i++) {
            Nru[i] = 0;
        }
    }

    return thisRet;
}

int getResult(int orderIdx) {
    if (orderIdx >= NP) return playGame();
    else {
        if (orderIdx == 3) orderIdx++;
        int maxRet = -1;
        for (int idx = 1; idx < NP; idx++) {
            if (!check[idx]) {
                check[idx] = true;
                orderP[orderIdx] = idx;
                int tmpRet = getResult(orderIdx + 1);
                if (tmpRet > maxRet) maxRet = tmpRet;
                check[idx] = false;
            }
        }
        return maxRet;
    }
}

int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < NP; j++) {
            scanf("%d", &inData[i][j]);
        }
    }
    check[0] = true;
    orderP[3] = 0;
    printf("%d\n", getResult(0));
    return 0;
}

실수

먼저 movePlayer 함수에서 각 루에 있는 선수를 옮길 때 1루(idx 0)부터 옮기기 시작했었는데 그렇게 되면 모든 선수가 홈까지 가게 되어버린다. 그래서 for loop를 3루(idx 2)부터 옮기도록 만들었다.

처음 orderP에 4번타자(idx 3)를 1번 선수로 할 때 1이 아닌 0으로 index를 시작하도록 만들었기 때문에 그렇게 했었어야 했는데 1을 넣어서 결과가 달라졌다.

playGame 함수에서 이닝이 진행됨에 따라 선수들의 타순이 이전에서 이어지게 되기 때문에 배열에 접근하는 index인 cur를 %를 이용해서 계속해서 이어지도록 만들었었다. 그런데 %를 할 때 선수들의 수 만큼 NP(9)로 했었어야 했는데 9까지 있다고 생각하고 10으로 했다.

index하는 데에서 어이없는 실수들이 많았고 이건 확실히 부족함이 있는 것이다. 어려운 문제가 아닌데 이런 부분에서 실수하지 않는 것도 실력이다.