백준 17281 ⚾

문제

---

17281번: ⚾ (acmicpc.net)

해결방법

---

• 순열을 통해 가능한 모든 타자 순서를 구한다.
  • nextPermutation을 사용하였다.
  • 이 때 근데 모든이닝에서 같은 결과를 내는 타자들을 중복하여 검사하지 않으면 더욱 효율적인 동작이 될 것 같다.
• 야구 게임을 구현하여 가능한 최댓 값을 구한다.
  • 구현은 크게 어렵지 않았다.
  • 주의할 점은 이닝 별로 함수를 구했는데 다음이닝의 첫 타자는 이전이닝의 마지막 타자 다음 타자가 들어가야 한다.

동작과정

---

1. nextPermutation을 사용하여 가능한 모든 타자 순서를 구했다. 이때 1번 선수는 항상 4번으로 한다.

2. 해당 타자 순서를 이용하여 얻을 수 있는 최댓값을 구한다.

코드

---

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

/*  순열을 이용한 구현 문제
 *
 */
public class Main {

    private static int N;

    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int[][] hits = new int[N][9];

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

        int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] hitters = new int[9];
        int result = 0;

        // 다음 순열을 찾고 게임을 실행하여 점수의 최댓값을 얻는다. 단 이때 4번타자는 항상 1번선수
        do{
            for(int i = 0; i < 3; i++)
                hitters[i] = numbers[i];

            hitters[3] = 0;

            for(int i = 4; i < 9; i++)
                hitters[i] = numbers[i-1];

            result = Math.max(result, play(hitters, hits));

        }while(np(numbers));

        out.write(result+"");
        out.flush();
    }

    // 게임을 수행하는 함수
    private static int play(int[] hitters, int[][] hits) {

        // 총 점수
        int score = 0;
        // 다음 이닝의 선두타자
        int hitter = 0;
        // 정해진 이닝만큼 진행
        for(int i = 0; i < N; i++) {
            int[] next = hit(hitter, hitters, hits[i]);
            hitter = next[1];
            score += next[0];
        }

        return score;
    }

    // 각 이닝에 대한 점수를 리턴 하는 함수
    private static int[] hit(int nextHitter, int[] hitters, int[] hits) {
        int out = 0;
        int score = 0;
        // 1, 2, 3 루에 주자가 있는지 나타냄
        boolean[] bases = new boolean[4];
        int hitter = nextHitter;

        // 아웃이 3개가 되기 전까지 수행
        while(out < 3) {
            // 현재 타자의 결과
            int hit = hits[hitters[hitter]];

            // 0이면 아웃
            if(hit == 0)
                out++;

            // 0이 아니면
            else {
                // 기존에 베이스에 있던 주자들을 3루부터 처리
                // 1루부터 처리하면 2, 3루에 주자가 없는 경우에 주자가 생기고 동시에 처리되어 버릴 가능성 존재
                for(int base = 3; base >= 1; base--) {
                    // 주자가 있을 때 주자가 hit 만큼 이동하고 이동한 값이 4를 넘으면 점수 추가 아니면 다시 bases 에 주자 표시
                    if(bases[base]) {
                        bases[base] = false;
                        int next = base + hit;
                        if (next >= 4)
                            score++;
                        else
                            bases[next] = true;
                    }
                }
                // 타자 처리
                if(hit == 4)
                    score++;
                else
                    bases[hit] = true;
            }

            // 다음 타자
            hitter = (hitter + 1) % 9;
        }

        // 현재 이닝에서 획득한 점수와 다음 타자를 리턴
        return new int[] {score, hitter};
    }

    // numbers 배열의 상태를 근거로 다음 순열 생성, 다음 순열 존재하면 true, 아니면 false
    private static boolean np(int[] numbers) {

        int N = numbers.length;

        // 1. 꼭대기 찾기
        int i = N - 1;
        while (i > 0 && numbers[i - 1] >= numbers[i]) {
            --i;
        }

        if (i == 0) {
            // 다음 순열을 만들 수 없는 이미 가장 큰 순열의 상태!
            return false;
        }

        // 2. 꼭대기의 바로 앞자리(i - 1)의 값을 크게 만들 교환값을 뒤쪽에서 찾기
        int j = N - 1;
        while (numbers[i - 1] >= numbers[j]) {
            --j;
        }

        // 3. i - 1 위치값과 j 위치값 교환
        swap(numbers, i - 1, j);

        // 4. i 위치부터 맨 뒤까지의 수열을 가장 작은 형태의 오름차순으로 변경
        int k = N - 1;
        while (i < k) {
            swap(numbers, i++, k--);
        }

        return true;
    }

    // 배열의 위치 변경
    private static void swap(int[] numbers, int i, int j) {
        int tmp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = tmp;
    }
}