[백준] ⚾야구 (JAVA)

⚾야구_17281

링크 : https://www.acmicpc.net/problem/17281

17281번: ⚾

문제 설명

이닝의 수가 N으로 주어진다.

9명의 타자가 있고 타자마다 각 이닝에 치는 m루타가 주어진다. (0은 스트라이크, 4는 홈런)

N = 2
1이닝 = 4 3 2 1 0 4 3 2 1
2이닝 = 1 2 3 4 1 2 3 4 0

감독이 순서를 마음대로 설정하여 최고의 점수를 얻어야한다.

다만 1번타자는 무조건 4번째 자리에 위치한다.

한번 정해진 타자의 순서는 모든 이닝 동일하게 설정된다.

점수의 최댓값을 구하는 문제이다.

 

---

문제 풀이

생각 과정

1번주자는 정해져있으므로 순서를 정하는 경우의 수는 8!

아웃이 3번 될때까지 최대 9명 주자를 반복해야 하므로 x3x9

라운드는 N (2~50)이므로 xN

 

시간복잡도가 8!x3x9xN이므로 브루트포스로가능 할 것이라 생각하고 풀었다.

타자들의 가능한 순서를 모두 구해서 각 순서마다 얻는 점수를 구하는 방식으로 구현을했다.

 

구현

public class 야구_17281 {
    static boolean[] visit, base;
    static int N,answer;
    static int[] order;
    static int[][] points;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());	//이닝 수
        order = new int[9];	// 순서
        points = new int[N][9];	// 각 이닝에 타자들의 친 루타
        visit = new boolean[9];	// dfs를 위한 중복방지 배열
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                points[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        visit[0] = true;	// 첫번째 타자 사용
        order[3] = 0;	// 첫번째 타자는 4번위치에 고정(3번인덱스)
        setOrder(0);
        System.out.println(answer);
    }
    public static void setOrder(int cur){	// 순서정하기
        if (cur == 9) {
            count();
            return;
        }
        if (cur==3) cur++;	// 4번위치는 이미 정해짐
        for (int i = 0; i < 9; i++) {
            if (!visit[i]){
                visit[i] = true;
                order[cur] = i;
                setOrder(cur+1);
                visit[i] = false;
            }
        }
    }
    public static void count(){
        int inning = 0;
        int cur = 0;
        int point = 0;
        base = new boolean[4];
        while (inning != N) {	// 모든 이닝 반복
            int out = 0;
            while (out != 3) {	// 아웃될때까지 반복
                if (cur==9) cur = 0;
                int c = order[cur++];
                if (points[inning][c] == 0) {
                    out++;
                } else {
                    point += getPoint(points[inning][c]);
                }
            }
            base = new boolean[4];
            inning++;
        }
        answer = Math.max(answer, point);
    }
    public static int getPoint(int p){	// 안타 쳤을 때 점수구하기
        int point = 0;
        base[0] = true;
        for (int i = 3; i >=0; i--) {
            if (base[i]){
                if (i + p > 3) {
                    point++;
                }else{
                    base[i+p] = true;
                }
                base[i]=false;
            }
        }
        return point;
    }
}

 

주의점

점수를 계산하는 방식에서 3루부터 계산을 해야한다.

1루부터 계산을 하면 중복된 계산이 발생하여 정확한 답이 나오지 않는다.