[BOJ/Java] 17281. ⚾

[BOJ/Java] 17281. ⚾

17281번: ⚾

---

문제 해석

이 문제는 야구 게임의 이닝과 플레이어의 타격 결과를 기반으로 최대 점수를 계산하는 문제이다. 각 선수가 타석에 서서 결과를 내는 순서인 타순을 조정하여 가장 많은 점수를 얻을 수 있는 경우를 찾아야 한다. 문제의 주요 요소는 다음과 같다

 

• 1번 선수는 항상 4번 타자로 고정.
• 나머지 선수들의 타순을 조합하여 최대 점수를 계산.
• 각 선수의 타격 결과에 따라 주자들이 진루하며, 홈을 통과하면 점수를 획득.

풀이 과정

제출된 코드는 선수들의 타순을 순열로 조합하고, 이 타순에 따라 실제 게임을 시뮬레이션하여 점수를 계산한다. startGame() 함수에서 게임의 각 이닝을 처리하고, 각 타석의 결과에 따라 주자들이 진루하거나 점수를 획득하는 로직을 구현하고 있다. 주요 로직은 다음과 같다

 

1. 각 타자의 타격 결과(graph[now][sel[s++%SIZE]])를 통해 주자 진루 및 점수 계산.
2. 비트마스킹을 사용하여 주자들의 위치와 점수 계산을 효율적으로 관리.

코드

package edu.ssafy.im.BOJ.Gold.G4.No17281;

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

public class Main {
    private int N; // 이닝 수
    private static final int SIZE = 9; // 선수 수
    private int[][] graph; // 각 이닝별 선수들의 결과
    private int[] sel; // 선택된 타순
    private int ans = Integer.MIN_VALUE; // 최대 점수

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().io();
    }

    private void io() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

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

        sol();
        sb.append(ans);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        sel = new int[SIZE];
        sel[3] = 0; // 1번 타자 타순 4번으로 고정
        permutation(0, 1 << 0);
    }

    private void permutation(int k, int v) {
        if (k == 3) k++; // 4번 타순 패스

        if (k == sel.length) {
            startGame(); // 게임 시작
            return;
        }

        for (int i = 1; i < SIZE; i++) {
            if ((v & (1 << i)) == 0) {
                sel[k] = i;
                permutation(k + 1, v | 1 << i);
            }
        }
    }

    private void startGame() {
        int res, score = 0, s = 0, chk = 0b0000111;
        for (int now = 0; now < N; now++) {
            int out = 0, v = 0;
            while(out < 3) {
                    res = graph[now][sel[s++%SIZE]];
                    if (res == 0) {
                        out++;
                    } else {
                        v <<= res; // 주자 진루
                        v |= (1 << res-1); // 새 주자 출발
                        for (int i = 3; i < 7; i++) {
                            if ((v & (1 << i)) != 0) score++;
                        }
                        v &= chk; // 홈을 통과한 주자들 제거
                    }
            }
        }
        ans = Math.max(ans, score); // 최대 점수 업데이트
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도는 순열을 통한 타순 조합에 의해 주로 결정된다. 타순 조합은 8! 경우의 수를 가질 수 있으며, 각 경우에 대해 N 이닝의 게임을 시뮬레이션한다. 따라서 최악의 경우 시간 복잡도는 𝑂(8!×𝑁)이 될 수 있다.

느낀점

비트마스킹과 순열을 활용한 복잡한 시뮬레이션 문제를 해결하는 과정은 매우 도전적이었다. 이를 통해 알고리즘 설계와 최적화 기법에 대한 이해를 더욱 심화할 수 있었다.