[Java] 백준 17281 ⚾

문제

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.
두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.
공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.
타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.

• 안타: 타자와 모든 주자가 한 루씩 진루한다.
• 2루타: 타자와 모든 주자가 두 루씩 진루한다.
• 3루타: 타자와 모든 주자가 세 루씩 진루한다.
• 홈런: 타자와 모든 주자가 홈까지 진루한다.
• 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.

한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.
 

입력

첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.

• 안타: 1
• 2루타: 2
• 3루타: 3
• 홈런: 4
• 아웃: 0

각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
 

출력

아인타팀이 얻을 수 있는 최대 점수를 출력한다.
 
문제 링크 : 야구공

---

설명

와... 정말 정말 오래걸린 문제다...ㅠㅠ
심지어 1시간 동안 풀었더니 문제 이해를 잘못하고 있었던...
그리고 1시간 이후부터는 답을 보면서 이해했는데 이해하는데 3시간 30분 걸림. 진짜 구현, 완탐이 약하긴 한가보다.
더 열심히 풀어봐야겠다.
 
심지어 if문으로 작성한건 틀리고 switch문으로 작성한건 맞아서 왜 안되는지 또 1시간 동안 코드 분석함..
 
각설하고 위 문제는 야구 룰을 잘 아신다면 설명은 쉽게 이해할 수 있다.
나는 야구 룰을 몰라서 많이 헤멨다.
 
처음에 내가 접근했던 방식은 예제로 주어진 입력n 개 중 최대값이 나오는 걸 골라서 n번의 이닝동안 반복하는 줄 알았다.
근데 전혀 아니였고, 선수들의 순서를 조합하여 n번의 이닝을 진행했을 때 받을 수 있는 최댓값을 찾는 문제이다.
 
문제 설명을 몇번 읽어봐도 잘 이해가 안되서 정말 많이 헤멨다.ㅠ
 
일단 1루, 2루, 3루를 거쳐 홈까지 오게되면 점수 + 1이다
그리고 문제에 1번 선수는 4번 타자로 정해져 있으니 순열을 구할 때 빼고 진행해도 된다.
 
조합이 아닌 순열을 구해야하는 이유는 맨 처음 홈런을 치고 2루타를 쳤을 값과 2루타를 치고 홈런을 치는 값 두 개가 다르기 때문이다.
따라서 순서에 따른 값이 달라지므로 순열로 구해야 한다.
 
나는 a라는 2차원 배열에 선수들의 결과를 저장했다.
그리고 place라는 1차원 배열에 선수들의 타순을 저장하고 check 배열에는 해당 자리에 선수가 있는지를 확인해줬다.
 
도움을 많이 받은 블로그 : https://yabmoons.tistory.com/284
 

코드

import java.io.*;
import java.util.*;

public class Test {
    static int[][] a;
    static int[] place;
    static boolean[] check;
    static int max = Integer.MIN_VALUE, n;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new int[n][9]; check = new boolean[9]; place = new int[9];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j= 0; j < 9; j++){
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        check[3] = true;	// 1번 선수는 4번 자리 지정(인덱스가 0부터 시작이므로 3에 저장)
        place[3] = 0;   // 타순
        dfs(1);

        System.out.println(max);
    }
    static void dfs(int depth){
        if (depth == 9){	// 8개의 자리가 완성되면 점수 계산
            score();
            return;
        }
        for (int i = 0; i < 9; i++){
            if (!check[i]){
                check[i] = true;
                place[i] = depth;
                dfs(depth + 1);
                check[i] = false;
            }
        }
    }

    private static void score() {
        int score = 0;	// 현재 자리에서 얻은 점수값
        int start = 0;	// 시작 위치

        for (int i = 0; i < n; i++){	// 이닝이 끝날 때까지
            int out = 0;	// 아웃 개수
            boolean[] vi = new boolean[3];	// 현재 1루,2루,3루에 선수 확인

            outer: while (true){
                for (int j = start; j < 9; j++){
                    int now = a[i][place[j]];	// 현재 선수의 상태

                    if (now == 0) out++;	// 아웃일 경우

                    else if (now == 1){		// 안타일 경우
                        if (vi[2]) score++;	// 3루에 선수가 있다면 홈으로 옴(점수 ++)
                        vi[2] = vi[1]; 		// 한칸씩 당겨줌
                        vi[1] = vi[0];
                        vi[0] = true;
                    }
                    else if (now == 2){		// 2루타일 경우
                        if (vi[2]) score++;
                        if (vi[1]) score++;
                        vi[2] = vi[0];
                        vi[1] = true;
                        vi[0] = false;
                    }
                    else if (now == 3){		// 3루타일 경우
                        if (vi[2]) score++;
                        if (vi[1]) score++;
                        if (vi[0]) score++;
                        vi[2] = true;
                        vi[1]=false;
                        vi[0]=false;
                    }
                    else if (now == 4){		// 홈런
                        if (vi[2]) score++;
                        if (vi[1]) score++;
                        if (vi[0]) score++;
                        vi[2] = false;
                        vi[1]=false;
                        vi[0]=false;
                        score++;
                    }
                    if (out == 3){		// 아웃이 3번일 경우
                        start = j + 1;
                        if (start == 9) start = 0;
                        break outer;
                    }
                }
                start = 0;	// 현재 9번 선수까지 다 진행했을 경우 다시 1번선수부터
            }
        }
        max = Math.max(score, max);
    }
}

이 문제를 풀고 타이머를 보니 이 시간..