[BOJ] - ⚾(야구) / 17281번 (Java)

[BOJ] - ⚾(야구) / 17281번 (Java)

 

[BOJ] - ⚾(야구) / 17281번 (Java)

 

1. 문제 접근

각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있으며, 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구하면 된다.

 

총 9명의 선수가 존재하고, 이 때 1번 선수는 4번 타자로 고정이다.

 

4번 타자가 고정이므로 총 8명의 선수를 줄세우는 경우의 수(8! = 40,320)가 존재한다.

 

따라서 제한 시간 내에 실행할 수 있으므로, permutation(순열)을 이용해 모든 타자의 순번을 결정하면 된다.

 

모든 타순을 결정했다면, 이는 기저조건이 되고 모든 이닝을 순회하며 점수 계산을 진행하면 된다.

 

예시로 2루타의 경우 점수 계산 방법은 아래와 같다.

 

case ANTA_2:
    // 3루에 주자가 있을 경우
    if (currInning.base3) {
        localScore++;
        currInning.base3 = false;
    }
    // 2루에 주자가 있을 경우
    if (currInning.base2) {
        localScore++;
        currInning.base2 = false;
    }
    // 1루에 주자가 있을 경우
    if (currInning.base1) {
        currInning.base3 = true;
        currInning.base1 = false;
    }
    currInning.base2 = true;
    break;

 

위와 같이 안타, 2루타, 3루타, 홈런에 대해 주자의 위치를 변경해주며, 득점이 발생할 경우, 더해주면 된다.

 

점수 계산 시, 각 베이스(1루, 2루, 3루)와 아웃 카운트를 저장할 클래스를 별도로 관리한다.

 

// 이닝 상태를 저장하는 클래스
static class GameState {
    boolean base1, base2, base3;
    int outCnt;

    public GameState(boolean base1, boolean base2, boolean base3, int outCnt) {
        this.base1 = base1;
        this.base2 = base2;
        this.base3 = base3;
        this.outCnt = outCnt;
    }
}

 

---

2. 코드

package boj;

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

/**
 * [BOJ] - ⚾(야구) / 17281번 
 * @author JinHxxxxKim
 * 
 * 1. 이닝 수 N(2 ≤ N ≤ 50)를 입력받는다.
 * 2. 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 입력받는다.
 * 3. 1번 선수가 4번 타자는 확정이므로, 8명의 선수에 대해 순열을 구한다.
 * 4. permutation
 * 		- selectIdx = 9 (기저조건)
 * 			- N개의 이닝에 대해 점수를 계산하고 더한다.
 * 			- 최대 점수를 갱신한다.
 */
public class Sol_17281 {
	private static final int ANTA_1 = 1;
	private static final int ANTA_2 = 2;
	private static final int ANTA_3 = 3;
	private static final int HOMERUN = 4;
	private static final int OUT = 0;

	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static int inning;
	private static int[][] playerResult;
	private static int ans;

	// 순열 관련 변수
	private static int[] selected;
	private static boolean[] isSelected;

	public static void main(String[] args) throws Exception {
		inning = Integer.parseInt(br.readLine().trim());
		playerResult = new int[inning][9];
		for (int inningCnt = 0; inningCnt < inning; ++inningCnt) {
			st = new StringTokenizer(br.readLine().trim());
			for (int playerCnt = 0; playerCnt < 9; ++playerCnt) {
				playerResult[inningCnt][playerCnt] = Integer.parseInt(st.nextToken());
			}
		}
		selected = new int[9];
		isSelected = new boolean[9];
		
		// 1번 선수는 4번 타자 고정
		isSelected[0] = true;
		permutation(0);
		System.out.println(ans);
	}

	private static void permutation(int selectIdx) {
		// 1번 선수는 4번 타자 고정
		if (selectIdx == 3) {
			selected[selectIdx] = 0;
			permutation(selectIdx + 1);
		}
		// 기저조건
		if (selectIdx == 9) {
			// 점수 계산
			int localScore = 0;
			int currPlayerIdx = 0;
			for (int inningCnt = 0; inningCnt < inning; ++inningCnt) {
				GameState currInning = new GameState(false, false, false, 0);
				// 3아웃이 되기 전까지 진행
				while (currInning.outCnt < 3) {
					int currplayer = selected[currPlayerIdx];
					switch (playerResult[inningCnt][currplayer]) {
					case ANTA_1:
						// 3루에 주자가 있을 경우
						if (currInning.base3) {
							localScore++;
							currInning.base3 = false;
						}
						// 2루에 주자가 있을 경우
						if (currInning.base2) {
							currInning.base3 = true;
							currInning.base2 = false;
						}
						// 1루에 주자가 있을 경우
						if (currInning.base1) {
							currInning.base2 = true;
							currInning.base1 = false;
						}
						currInning.base1 = true;
						break;
					case ANTA_2:
						// 3루에 주자가 있을 경우
						if (currInning.base3) {
							localScore++;
							currInning.base3 = false;
						}
						// 2루에 주자가 있을 경우
						if (currInning.base2) {
							localScore++;
							currInning.base2 = false;
						}
						// 1루에 주자가 있을 경우
						if (currInning.base1) {
							currInning.base3 = true;
							currInning.base1 = false;
						}
						currInning.base2 = true;
						break;
					case ANTA_3:
						// 3루에 주자가 있을 경우
						if (currInning.base3) {
							localScore++;
							currInning.base3 = false;
						}
						// 2루에 주자가 있을 경우
						if (currInning.base2) {
							localScore++;
							currInning.base2 = false;
						}
						// 1루에 주자가 있을 경우
						if (currInning.base1) {
							localScore++;
							currInning.base1 = false;
						}
						currInning.base3 = true;
						break;
					case HOMERUN:
						if (currInning.base3) {
							localScore++;
							currInning.base3 = false;
						}
						// 2루에 주자가 있을 경우
						if (currInning.base2) {
							localScore++;
							currInning.base2 = false;
						}
						// 1루에 주자가 있을 경우
						if (currInning.base1) {
							localScore++;
							currInning.base1 = false;
						}
						localScore++;
						break;
					case OUT:
						currInning.outCnt++;
						break;
					}
					// 다음 타자로 교체
					currPlayerIdx = (currPlayerIdx + 1) % 9;
				}
			}
			ans = Math.max(ans, localScore);
			return;
		}

		for (int elementIdx = 1; elementIdx < 9; ++elementIdx) {
			if (isSelected[elementIdx])
				continue;

			// 전처리
			isSelected[elementIdx] = true;
			selected[selectIdx] = elementIdx;
			// 재귀
			permutation(selectIdx + 1);
			// 후처리
			isSelected[elementIdx] = false;

		}
	}

	// 이닝 상태를 저장하는 클래스
	static class GameState {
		boolean base1, base2, base3;
		int outCnt;

		public GameState(boolean base1, boolean base2, boolean base3, int outCnt) {
			super();
			this.base1 = base1;
			this.base2 = base2;
			this.base3 = base3;
			this.outCnt = outCnt;
		}

	}
}

 

---

3. 디버깅

선수의 명 수가 9명으로 고정 + 4번 타자 고정이라는 힌트를 이용해 순열을 이용해 구현하였으며, 이닝의 상태를 정확하게 관리하기 위해 별도의 `GameState`클래스를 선언해 사용했다.

 

또한, 각 상황(안타, 2루타, 3루타, 홈런)에 대해 정확하게 시뮬레이션 돌려보고 구현하는 것이 중요한 것 같다.

---

4. 결과