BOJ_17281 : ⚾

👉 문제링크

17281번: ⚾

---

---

🔸 문제 분석 🔸

• n개의 이닝 별 타자의 성적을 입력받고, 나올 수 있는 최대 득점을 출력한다.
  • 타자는 9명이며 4번 타자는 1번 선수로 고정되어 있다.
  • 한 번 정해진 타순은 모든 이닝에 똑같이 적용된다.
  • 한 이닝에서 사용한 타순을 다음 이닝에서 이어서 적용한다.
  • 0은 아웃이고, 1~4는 안타, 2루타, 3루타, 홈런이다.
• 4번 타순을 제외하고, 8자리의 순서를 뽑는 순열을 구해 타순을 모두 비교한다.
• 각 타순 별 점수 결과를 계산하고 그 중 최대값을 출력한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][] inning_point;
    static int[] player;
    static boolean[] used;
    static int n, max;

    private static void perm(int idx) { // idx : 골라야 하는 타순
        if (idx == 10) {
            baseBall();
            return;
        }

        if (idx == 4) {
            perm(idx + 1); // 4번자리 스킵
        } else {
            for (int i = 2; i <= 9; i++) {
                if (!used[i]) {
                    used[i] = true;
                    player[idx] = i;
                    perm(idx + 1);
                    used[i] = false;
                }
            }
        }
    }

    private static void baseBall() {
        int point = 0;
        int player_num = 1;
        for (int i = 1; i <= n; i++) {
            int out = 0;
            Queue<Integer> lu = new ArrayDeque<>();
            while (out < 3) {
                if (inning_point[i][player[player_num]] == 0) {
                    out++;
                } else {
                    int size = lu.size();
                    for (int k = 0; k < size; k++) {
                        int man = lu.poll() + inning_point[i][player[player_num]];
                        if (man > 3) {
                            point++;
                        } else {
                            lu.add(man);
                        }
                    }

                    if (inning_point[i][player[player_num]] == 4) {
                        point++;
                    } else {
                        lu.add(inning_point[i][player[player_num]]);
                    }
                }

                if (++player_num == 10) {
                    player_num = 1;
                }
            }
        }

        max = Math.max(max, point);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        player = new int[10];
        used = new boolean[10];
        player[4] = 1;
        used[1] = true;

        inning_point = new int[n + 1][10];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 9; j++) {
                inning_point[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        perm(1);

        System.out.println(max);
    }
}

🔸 코드 해석 🔸

• 각 이닝 별 타자의 성적을 2차원 배열 inning_point에 저장한다.
• perm() 메서드에서 8자리 타순에 대한 순열을 만들어 계산한다.
  • 뽑은 타순은 player 배열에 저장하고, used의 해당 인덱스를 true로 바꾼다.
  • perm() 메서드를 불러 재귀 형식으로 순열을 완성한다.
• 순열이 완성되면 baseBall()메서드를 호출해 야구 경기 결과를 계산한다.
  • 각 베이스의 상태를 큐 lu를 통해 관리한다.
    • 타자가 공을 치고, 그 결과 만큼 기존의 상태들에 더해준 뒤 현재 타자 값도 추가해준다.
    • 최소 1개씩 당기기부터 4 홈런으로 모두 나가기 까지 있으며, lu는 항상 내림차순이다.
    • 홈으로 나간 타자의 수를 카운트한다.
    • out이 3번되면, 한 이닝을 종료한다.
    • 모든 이닝이 종료되면 홈으로 도달 한 타자의 수와 max 값 중 큰 값을 max로 저장한다.

---

🔸 end 🔸

• 순열과 야구 규칙에 대한 구현이 섞인 문제였다.
• 차분히 풀면 그렇게까진 어렵지 않았는데, 중간중간 끊어서 풀다보니 더 늘어진 것 같다.
• 베이스 별 상태를 큐로 관리했는데, boolean이나 int 배열로도 가능한 것 같다. 코드는 많이 길어지지만 큐보다 빠르다.