[백준 / BOJ] 17281 ⚾ (야구)

문제

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

17281번: ⚾

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다.

 

게임은 N개의 이닝으로 이루어져있다.

우리는 9명이 선수가 각 이닝에 얻는점수를 알고있다.

각 선수의 순서를 적절히 배치하여 (1번부터 9번까지) 얻을수있는 최대 점수를 구하는 문제다.

 

---

풀이

완전탐색으로 푼 문제다.

 

모든 선수의 배치가능한 조합을 구한후, 구해진 조합을 토대로 점수를 구하면 된다.

선수는 9명이지만, 1번선수가 무조건 4번째로 공격하므로, 배치하는 경우의 수는 8!이 된다.

 

로직

1. 선수를 배치하는 모든 경우의 수를 구한다 (8!)

    private void makePlayerSet(int idx){
        if(idx > 9){
            score = Math.max(score, getScore(1, 0));
            return;
        }
        if(idx == 4){
            playerSet[4] = 1;
            makePlayerSet(idx+1);
            return;
        }
        for(int i = 2; i <= 9; i++){
            if(check[i]) continue;
            check[i] = true;
            playerSet[idx] = i;
            makePlayerSet(idx+1);
            check[i] = false;
        }
    }

2. 배치된 선수를 기준으로 1이닝부터 N이닝까지 반복하며 점수를 구한다.

 

    private int getScore(int inning, int playerIdx){
        if(inning > N) return 0;
        int score = 0, outStack = 0;
        Queue<Integer> scoreStack = new LinkedList<Integer>();
        while(outStack < 3){
            playerIdx++;
            if(playerIdx > 9) playerIdx = 1;
            if(player[inning][playerSet[playerIdx]] == 0){
                outStack++;
                continue;
            }
            if(player[inning][playerSet[playerIdx]] == 4){
                score += setScore(scoreStack, 4) + 1;
                continue;
            }
            score += setScore(scoreStack, player[inning][playerSet[playerIdx]]);
            scoreStack.add(player[inning][playerSet[playerIdx]]);
        }
        return score+getScore(inning+1, playerIdx);
    }

 

최악의 경우 (8!*4*N*30)번 반복해서 시간초과가 나올것이라 예상했는데, 풀렸다

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/17281%20%E2%9A%BE/Main.java

devxb/JJUNalgo