[백준 17281] - ⚾[JAVA](골드4)

문제

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

17281번: ⚾

 

문제 풀이

접근방법에 대해서 많은 고민을 했었다.  

시간제한이 1초이고, 이닝의 최대수가 50이며, 순서를 결정해야 하는 타자의 명수는 8명이었다.

그렇다면 시간복잡도는 50*8!*@인데, 시간복잡도가 1초는 안넘길거 같아서

타자의 대한 모든 경우의 수를 계산해도 문제가 되지 않을것이라고 판단했다.

8P3인 이유는 4번 타자는 첫번째 선수로 결정되었기 때문이다.

 

순열에 대한 코드는 정말 간단하다.

visit 배열을 통해서 포함되었는지, 아닌지를 판단해서 배열에 넣어준다.

기존 player 배열에 4번 인덱스는 1번 타자로 고정시키고, visit [4]도 true이며, 해당 값은 절대 바뀌지 않는다.

이렇게 순열을 통해서 선수에 대한 타순이 결정되었다면 그 다음은 경기 진행방식이다.

경기진행방식은 야구랑 다를게 없다.

아웃카운트가 3개되면 이닝이 종료되고, 종료된 타자에 다음 타자가 이닝을 시작한다.

그러기 위해서 이닝마다 마지막타자를 기억해야 했다.

그리고 9번 타자까지 진행하고, 1번 타자로 돌아가야 하기 때문에

now = (now%9)+1

위 코드를 통해서 1~9번까지의 타순을 강제시켰다.

 

그다음은 타자가 친 공에 대한 베이스 이동이었다.

 

타자가 친 공은 0,1,2,3,4에 따라서 베이스 전진이 다르다.

여기서 공통점은

1. 아웃(0)은 모든 주자가 0루를 전진하고, 아웃 카운트가 증가
2. 1루타(1) 모든 주자가 1루를 전진
3. 2루타(2)는 모든 주자가 2루를 전진
4. 3루타(3)는 모든 주자가 3루를 전진
5. 홈런(4)은 모든 주자가 홈으로 돌아온다.

즉 숫자에 따라서 베이스를 전진한다는 것이다.

for(int h=0; h<hit; h++){
    mybase.base[4] += mybase.base[3];
    mybase.base[3] = mybase.base[2];
    mybase.base[2] = mybase.base[1];
    mybase.base[1] = 0;
}

위 코드를 통해서 베이스에 있는 주자들을 전진했다.

왜 1루는 항상 0인가에 대해서 얘기를 해보면 1루로 전진을 하는 타자는 현재 타자이지, 베이스에 있는 타자들이 아니다.

따라서 항상 1루는 비워준다.

for문을 들어간다는 조건은 hit가 1 이상이기 때문에 치기만 한다면 모든 주자들은 전진을 하기 때문이다.

4번에서 계속 더해주는 이유는 4번에 들어가는 사람의 수가 곧 점수이기 때문이다.

나머지 루는 한 칸씩 당겨주는 역할을 한다.

 

그렇다면 현재 친 타자는 어떻게 전진시키냐?

mybase.base[hit]++;

hit은 타자가 친 루타를 의미한다. 1루타를 쳤으면 1루 베이스로 전진, 2루면 2루로 전진, 홈런이면 그대로 점수로 직행된다.

이렇게 한 이닝이 끝나면 홈에 들어온 주자의 수가 곧 점수로 직결된다.

 

세세한 코드는 전체 코드에 대한 주석으로 이해하면 될 것이다.

 

전체 코드

import javax.print.attribute.standard.Finishings;
import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static int N;

    static int[][] graph;

    static Base mybase = new Base();
    static int[] player = new int[10];
    static boolean[] visit = new boolean[10];
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        player[4] = 1;
        visit[4] = true;
        makePermutation(9, 2);
        System.out.print(answer);
    }

    public static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        graph = new int[N + 1][10];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 9; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    public static int goGame() {
        int score = 0;
        int now = 1;
        for (int i = 1; i <= N; i++) {
            int out = 0;
            mybase.init();
            while (out != 3) { // out이 3이 될때 종료
                int hit = graph[i][player[now]]; // 몇루타인지
                now = (now % 9) + 1; // 다음타순
                if (hit == 0) {
                    out++;
                    continue;
                }
                for (int h = 0; h < hit; h++) { // 잔루 주자 땡기기
                    mybase.base[4] += mybase.base[3];
                    mybase.base[3] = mybase.base[2];
                    mybase.base[2] = mybase.base[1];
                    mybase.base[1] = 0;
                }
                mybase.base[hit]++; //현재 친 루만큼 현재 주자 전진
            }
            score += mybase.base[4]; //이닝이 끝나고 홈에 쌓인 주자들 더하기
        }
        return score;
    }

    public static void makePermutation(int limit, int count) {
        if (limit + 1 == count) { //다 뽑을 경우
            answer = Math.max(answer, goGame());
            return;
        }
        for (int i = 1; i <= 9; i++) {
            if (!visit[i]) {
                player[i] = count;
                visit[i] = true;
                makePermutation(limit, count + 1);
                visit[i] = false;
            }
        }
    }

    static class Base {
        int[] base = new int[5];

        public void init() {
//            for(int b : this.base){
//                b = 0;
//            }
            for (int i = 0; i < 5; i++) {
                base[i] = 0;
            }
        }
    }
}