[JAVA] 백준 17281번 : ⚾

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

 

---

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

public class Main {
	static int N, maxScore = 0; //이닝 수, 픽스된 선수 숫자
	static int[] seq = new int[9];//선발 순서
	static boolean[] checked = new boolean[9], base = new boolean[4]; //사용된 선수
	static int[][] pResult;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		seq[3] = 0; //4번째 타자로 1번 선수
		checked[0] = true;
		
		//선수 점수 기록
		pResult = new int[N][9];
		for (int i = 0; i < N; i++) {
			pResult[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		}
		
		setPlayer(0);
		System.out.println(maxScore);
	}
	
	private static void setPlayer(int idx) {
		if(idx == 9) {
			maxScore = Math.max(maxScore, playGame());
			return;
		}
		if(idx == 3) {
			setPlayer(idx+1);
			return;
		}
		for (int i = 0; i < 9; i++) {
			if(!checked[i]) {
				seq[idx] = i;
				checked[i] = true;
				setPlayer(idx + 1);
				checked[i] = false;
			}
		}
	}
	private static int playGame() {
		int score = 0;
		int p = 0; //seq[p] 선수부터 시작
		
		for(int n = 0; n < N; n++) { //n번째 이닝에 대해 게임 진행
			Arrays.fill(base, false);; //야구 루 현황 (0 = 홈런, i루)
			int out = 0;
			
			while(out < 3) {
				//게임 진행
				int pNum = seq[p];
				int result = pResult[n][pNum];
				if(result == 0) {
					out++;
				} else {
					score += getScore(pNum, result);
				}
				p = (p + 1) % 9;
			}
		}
		return score;
	}
	private static int getScore(int pNum, int point) {
		int c = 0;
		base[0] = true;
		
		if(point != 4) {
			for(int i = 3; i >= 4 - point; i--) {
				if(base[i]) {
					c++;
					base[i] = false;
				}
			}
			for (int i = 3 - point; i >= 0; i--) {
				base[i+point] = base[i];
				base[i] = false;
			}
		} else { //홈런의 경우
			for(boolean e : base) {
				if(e) c++;
			}
			Arrays.fill(base, false);
		}
		return c;
	}
	
}

💡 브루트포스, 구현

풀이

 

야구 모르는 사람(=나)를 위한 정리. 기본적으로 이 문제는 공격하는 경우만 고려한 문제인 듯 (매 이닝마다 공격이라고 생각)

• 한 게임에서 아웃이 3번 일어나면, 해당 이닝은 끝 -> 공/수 교대 후 새 이닝 진행 (근데 입력값엔 그냥 공격의 경우만..)
• 타순은 한번 정해지면 N번의 이닝동안 동일하다.
  • 즉, 완탐으로 타자 구성을 픽스한 다음, 그 순서대로 게임을 N번 돌려 최종 점수 산출 및 갱신
• 입력값으로 주어지는 각 줄은 각 이닝마다 각 선수별 능력치(고정값)을 의미한다. 같은 이닝 안에선 몇번이고 동일한 결과를 낸다 (안타 선수는 항상 안타만, 홈런 선수는 항상 홈런만...)
  • n번째 이닝(= n번째 줄 포맷)은 아웃이 3이 될 때 까지 지속된다.
  • 해당 이닝에서 마지막 타자 순서를 기억했다가, 다음 이닝에서 그 다음부터 시작한다.
  • 예를 들면, [0 4 4 4 4 4 4 4 4] 가 입력 값으로 주어졌다면, k번째 이닝에서는 이 포맷으로 계속 도는거
    • 만약 시작점이 arr[1] 부터 시작이면 (4 * 8) * 3 이런 방식 0이 3번 나올 때 까지 돔
    • 그 다음 이닝에서는 arr[0]을 마지막으로 끝났으니 arr[1] 부터 시작함
• 득점은 한 선수가 홈(0)으로 들어올 때 마다 1점씩 얻는다

---

시간초과로 계속 고통 받다가... 베이스에 나와있는 선수들을 저장하는 base배열의 자료형을 int[]에서 boolean[]으로 바꾸고, 초기화 방법을 새로 할당하는 것에서 fill()로 초기화 하는 것으로 변경해서 겨우 통과했다

! boolean 배열과 int 배열의 시간 차이가 생각보다 크다. 굳이 필요한 상황이 아니라면 boolean[] 을 사용해 체크할 것
! 배열을 초기화 할때는 new로 새로 할당하는 것 대신 Arrays.fill( ) 메서드를 활용해 초기화하자

 

흐름

1. 브루트포스로 선수 순서 고정 : 9명 모두 할당 되면 게임 시작
2. 게임을 진행한다.
   • 매 이닝마다 out 변수, base 배열은 초기화 필수 (Arrays.fill() 로 초기화), 타자 번호인 p는 초기화 X (이어서 하므로)
   • base 배열 : 0(홈), 1(1루) ... 각각의 위치에 선수가 있는지 체크 (단순히 존재 여부만 체크하면 되므로 boolean 배열로도 충분하다)
   • 점수 & 현재 base 상태를 고려해 총 몇명이 홈에 들어오는지 계산
     • base[0] = true로 시작 (타자가 공 날리고 이동해야되므로)
     • 홈에 도착할 예정인 선수들의 수를 세고, 해당 자리는 false로 비워주기
     • 이후 베이스에 남아있는 선수들 위치 옮겨주기 (마찬가지로 원래 자리는 비워줌)
   • out이 3이 되면 해당 이닝 끝, 다음 이닝으로 넘어감
3. 최종 점수를 maxScore(최대 점수)와 비교해 갱신