[백준] 17281. ⚾

문제 링크

[백준] 17281. ⚾

풀이 과정

시뮬레이션 문제이며, 타자를 세울 수 있는 모든 경우를 완전 탐색하며 답을 찾아야 합니다.

아래는 제가 문제를 풀면서 빠뜨렸던 규칙입니다.

1. 아웃이 3번될때까지 이닝은 계속된다. 다음 타자가 나와서 침.
2. 4번 타자는 1번 선수다. 즉, 1번 선수가 무조건 네 번째로 친다.

picked[3] = 0;
used[3] = true;

perm(1);

4번 타자를 먼저 줄 세운 뒤, 순열을 구하는 메소드를 호출해 타자를 줄세웁니다.

static void perm(int idx) {
    if (idx == 9) {
        calc();

        return;
    }

    for (int i = 0; i < 9; i++) {
        if (!used[i]) {
            used[i] = true;
            picked[i] = idx;

            perm(idx + 1);

            used[i] = false;
        }
    }
}

perm 메소드 는 9명의 타자가 그라운드에 설 수 있는 모든 순서 경우의 수를 구합니다. 로직은 다음과 같습니다.

• 인덱스 9로 호출 될 시, 이는 타자의 순번이 모두 정해진 경우입니다. calc 메소드 를 호출해 최대 점수를 구합니다.
• 아직 줄을 다 못세운 경우, 함수를 더 돌립니다.

static void calc() {
    int score = 0;
    int strikerIdx = 0;

    for (int inning = 0; inning < N; inning++) {
        Arrays.fill(roo, false);
        int outCnt = 0;

        while (outCnt < 3) {
            int command = info[inning][picked[strikerIdx]];

            switch (command) {
                case 0:
                    outCnt++;
                    break;
                case 1:
                    score += move(1);
                    break;
                case 2:
                    score += move(2);
                    break;
                case 3:
                    score += move(3);
                    break;
                case 4:
                    score += move(4);
                    break;
            }

            strikerIdx = (strikerIdx + 1) % 9;
        }
    }

    answer = Math.max(answer, score);
}

calc 메소드 는 모든 이닝을 진행시켜 점수를 구하는 과정을 진행합니다. 로직은 다음과 같습니다.

3아웃 될 때까지 아래 과정을 계속 반복합니다.

1. 타자가 공을 친 결과를 변수 command 로 가져옵니다.
   1. 아웃이면 outCnt 를 증가시킵니다.
   2. 안타(1)면, 루의 모든 주자를 1칸씩 이동시키기 위해, 1을 파라미터로 move 메소드 를 호출합니다.
   3. 2루타(2)면, 루의 모든 주자를 2칸씩 이동시키기 위해, 2를 파라미터로 move 메소드 를 호출합니다.
   4. 3루타(3)면, 루의 모든 주자를 3칸씩 이동시키기 위해, 3를 파라미터로 move 메소드 를 호출합니다.
   5. 홈런(4)이면, 루의 모든 주자를 홈으로 빼기 위해, 4를 파라미터로 move 메소드 를 호출합니다.
2. 다음 타자를 설정합니다.

static int move(int delta) {
    roo[0] = true;
    int hitScore = 0;
    int size = 4;

    while (size-- > 0) {
        if (roo[size]) {
            roo[size] = false;

            if (size + delta >= 4) {
                hitScore++;
                continue;
            }

            roo[size + delta] = true;
        }
    }

    return hitScore;
}

move 메소드 는 루에 있는 주자들을 delta 칸만큼 전진시키는 과정을 진행합니다. 로직은 다음과 같습니다.

1. 현재 타자도 전진시키기 위해 roo[0] 을 true 로 설정합니다.
2. 홈에 가장 가까운 3루부터 거꾸로 타자들을 delta 만큼 앞으로 전진시킵니다.
   • 더해서 4 이상이면, 홈에 도착한 것이므로 점수를 증가시킵니다.
   • 홈에 도착 못하면 전진한 루에 주자를 표시합니다.
3. 공은 친 결과로 인해 얻은 점수( hitScore) 를 리턴합니다.

코드

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

public class Main {
    static int N;
    static int[][] info;
    static int[] picked;
    static boolean[] used;
    static boolean[] roo = new boolean[4];
    static int answer;

    public static void main(String[] args) throws IOException, InterruptedException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        info = new int[N][9];
        picked = new int[9];
        used = new boolean[9];

        for (int i = 0; i < N; i++) {
            info[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        picked[3] = 0;
        used[3] = true;

        perm(1);

        System.out.println(answer);
    }

    static void perm(int idx) {
        if (idx == 9) {
            calc();

            return;
        }

        for (int i = 0; i < 9; i++) {
            if (!used[i]) {
                used[i] = true;
                picked[i] = idx;

                perm(idx + 1);

                used[i] = false;
            }
        }
    }

    static void calc() {
        int score = 0;
        int strikerIdx = 0;

        for (int inning = 0; inning < N; inning++) {
            Arrays.fill(roo, false);
            int outCnt = 0;

            while (outCnt < 3) {
                int command = info[inning][picked[strikerIdx]];

                switch (command) {
                    case 0:
                        outCnt++;
                        break;
                    case 1:
                        score += move(1);
                        break;
                    case 2:
                        score += move(2);
                        break;
                    case 3:
                        score += move(3);
                        break;
                    case 4:
                        score += move(4);
                        break;
                }

                strikerIdx = (strikerIdx + 1) % 9;
            }
        }

        answer = Math.max(answer, score);
    }

    static int move(int delta) {
        roo[0] = true;
        int hitScore = 0;
        int size = 4;

        while (size-- > 0) {
            if (roo[size]) {
                roo[size] = false;

                if (size + delta >= 4) {
                    hitScore++;
                    continue;
                }

                roo[size + delta] = true;
            }
        }

        return hitScore;
    }
}