[백준 17281] ⚾

오늘 알고리즘 스터디에서 17281번 ⚾ 문제를 풀었다.
이번 스터디 주제는 골드 이상 브루트포스 였다.

입력으로 다음이 주어졌을 때,

• 이닝 수,
• 각 선수가 각 이닝에서 얻는 결과
  (안타 : 1, 2루타 : 2, 3루타 : 3, 홈런 : 4, 아웃 : 0)

다음을 출력해야하는 알고리즘을 작성하는 문제였다.

• 타순을 고정했을 때, 팀이 얻을 수 있는 최대 점수
  단, 4번 타자는 무조건 0번선수

---

첫번째 아이디어

잘못되긴 했지만, 내가 처음 생각했던 로직이다.

아이디어의 출발은 다음과 같았다.
애초에 아웃은 무조건 나중순서인게 유리하고, 1,2,3루타가 있을 때 홈런은 무조건 뒷순서인게 유리하고, 1루타보다 3루타가 뒷순서인게 유리하기 때문에, 유리한 순서를 다음과 같이 지정할 수 있다.

1루타 < 2루타 < 3루타 < 홈런 < 아웃

따라서,

• 모든 이닝을 통틀어서 아웃카운트가 제일 많은 선수를 맨 뒤 타순으로 빼고
• 모든 이닝을 통틀어서 아웃카운트가 제일 많은 선수를 그이전 타순으로 빼고
• 3,2,1루타 순서대로 그 이전 타순으로 빼는 방법

하지만 이내 이 로직은 잘못되었다는 점을 깨달았다. 왜냐면,

• 애초에 타순이 다음 이닝으로 이어진다. 따라서 아웃을 맨 뒤로 빼더라도 다음 이닝에서 앞부분에서 시작할 수도 있으므로, “모든 이닝”을 한줄로 생각하고 order를 배열했을 때 가장 높은 점수가 나오는 order를 골라야 하는것임.
• 홈런이 없는이닝도 있음. 이러면 “유리한 순서” 자체가 달라짐.
• 홈런이 있는경우라면 홈런을 무조건 뒤로 빼는게 맞긴 하지만, 이닝마다 홈런 위치도 달라지고, 홈런이 없으면 1,2,3루타 순서도 다 고려되어야 하니깐

두번째 아이디어

브루트 포스 문제답게, 정말 완전탐색으로 푸는 방법이다.
내 아이디어는, 완전 탐색으로 8! 개의 모든 순열을 조회하고, 각 순열마다 점수를 계산해서 최대점수를 업데이트 하는 방법이었다.

• 완전탐색 : 백트래킹 사용
• 점수 계산은 홈부터 3루베이스 까지 각 베이스의 선수 상태를 나타내는 배열int[] ru = {0,0,0,0}; 을 선언하고 매번 이 배열을 순회 및 수정하여 계산하였다.

package prob17;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class DayProb17 {

    private static int N;
    private static int[][] scores;
    private static int[] order = new int[9];
    private static boolean[] used = new boolean[9];
    private static int max = 0;

    public static void main (String[] argv) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;

        scores = new int[N][9];

        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++){
                scores[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        used[0] = true;
        makeOrder(0);

        System.out.println(max);

    }

    // 백트래킹으로 가능한 모든 순열에서 점수 계산
    private static void makeOrder(int now){
        // 4번 타자는 이미 1번 선수로 확정됨.
        if (now == 3) {
            makeOrder(now + 1);
        }
        if (now == 9) {
            // 계산 후 최대점수 업데이트
            int thisScore = calScore();
            if (thisScore > max){max = thisScore;}
        }
        for (int i = 1; i < 9; i++){
            if (used[i]) {continue;}
            order[now] = i;
            used[i] = true;
            makeOrder(now + 1);
            used[i] = false;
            order[now] = 0;
        }
    }

    private static int calScore(){
        int score = 0;
        int p = 0;

        // 이닝
        for (int j = 0; j < N; j++){
            int[] ru = {0,0,0,0};
            int outcount = 0;

            while (outcount < 3){
                int player = order[p % 9];

                if (scores[j][player] == 0) {
                    outcount++;
                } else if (scores[j][player] == 4){
                    ru[0] = 1;
                    for (int i = 0; i < 4; i++){
                        score += ru[i];
                        ru[i] = 0;
                    }
                } else {
                    ru[0] = 1;
                    int ruta = scores[j][player];
                    for (int i = 3; i >= 0; i--){
                        if (ru[i] == 0){continue;}
                        if (i + ruta >= 4){
                            score++;
                            ru[i] = 0;
                        } else {
                            ru[i] = 0;
                            ru[i + ruta] = 1;
                        }
                    }
                }

                p++;
            }
        }
        return score;
    }
}

브루트포스문제긴 했지만 너무 무작정 8! 을 다 조회해야해서 시간초과가 뜨지않을까 걱정했는데 시간초과가 뜨지 않았다.

생각해보면,
백트래킹에 8! 번의 반복,
각 순열마다 O(N) * O(27) 의 반복.
(아웃카운트가 맨마지막 타자한테서만 잡힌다고 가정했을 때 9*3=27, 이닝 수 N)
최대 반복 횟수가 8! * 27 * N 번인 셈이다.

8!은 계산해보면 약 4만 가지로, 생각보다 그렇게 반복수가 많지가 않다. 그래서 그냥 이렇게 모든 순열을 다 조회하라는 목적으로 낸 문제가 맞는거 같고,
그렇게 하지 않으면 사실상 매 이닝마다 달라지는 선수의 방망이 결과와, 다음 이닝에도 유지되는 타순을 개별로 고려할 수가 없기도 하다.

챗지피티의 의견

정석 풀이 자체는 : 완전탐색 + 이닝 점수 시뮬레이션이 맞다고 합니다.

• 타순을 생성하는 완전탐색은 백트래킹 추천,
• 이닝 점수 시뮬레이션은 베이스상태의 비트마스크 갱신을 추천한다고 합니다.
  (빠르고 실수가 적은 방법)

⇒ 시간복잡도는 8! (완탐) * O(N) (시뮬레이션)

⇒ 완전탐색 자체는 백트래킹 등으로 구현하여 코드 자체는 고정적이기 때문에 효율자체에 큰 영향은 미치지 않지만, 각 완전탐색 내부에서 시뮬레이션 (점수 계산) 방식이 효율을 결정하게될 것임.

내말이 맞았다.

세번째 개선

챗지피티의 추천대로 계산 시뮬레이션시 비트마스크를 사용해보기로 했다.
내가 기존에 짰던 코드는 길이 4짜리의 int 배열을 매번 수정하고 조회해야했으므로 그러는데 걸리는 시간 cost가 상당히 높았을 것이다.

• 계산 시뮬레이션 시 → 비트마스크 사용
• 기존에 배열로 사용했던 int[] ru = {0,0,0,0}; 를, 그냥 비트마스크용 integer 하나로 계산했으며, ru 배열 순회도 필요없이 그냥 비트연산으로 진행함.
• Integer.bitCount(ru) 현재 베이스에 서있는 선수 수
• Integer.bitCount(ru >> 4) 홈을 통과한 선수 수 (득점함)
• ru & 0b1110 홈을 통과한 선수 (5자리 이상의 비트) & 홈 선수 (타자) 지우기
• ru << ruta N루타 만큼 진루

    private static int calScore(){
        int score = 0;
        int p = 0;

        // 이닝
        for (int j = 0; j < N; j++){
            int ru = 0; // 비트마스크로 관리 예정
            int outcount = 0;

            while (outcount < 3){
                int player = order[p % 9];
                int ruta = scores[j][player];

                if (ruta == 0) {
                    outcount++;
                } else if (ruta == 4){
                    score += (Integer.bitCount(ru) + 1);
                    ru = 0;
                } else {
                    ru = (ru | 1) << ruta;
                    score += Integer.bitCount(ru >> 4);
                    ru = 0b1110 & ru;
                }

                p++;
            }
        }
        return score;
    }
}

결론적으로 계산 시뮬레이션 (타순 별 점수 계산) 부분만 고쳤음에도 시간과 메모리 효율 모두 거의 반이 절약되었다.

• 매 순열 재귀스택마다 생성되는 타선 배열의 메모리공간 절약
• 타선 배열 접근 시간, 순회 시간, 수정 시간 절약