[골드4] 17281. ⚾ (Java)

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

17281번: ⚾

⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾⚾

 

---

※  문제를 요약하면 아래와 같습니다.

▶ 야구에서 임의의 감독이 타자 9명을 순서를 배정했을 때 얻을 수 있는 최대 점수 찾기 

▶ 각 이닝별로 1~9번의 선수가 아웃, 안타, 2루타, 3루타, 홈런 중 하나의 경우를 반드시 가짐

▶ 아웃 == 0, 안타 == 1, 2루타 == 2, 3루타 == 3, 홈런 == 4

▶ 이닝의 횟수는 2~50 사이이며, 아웃 카운트는 3으로 고정

▶ 1번 선수는 반드시 4번 타자로 고정 (감독이 좋아함)

▶ Input : 첫번 째 줄에 이닝 수 N이 주어지며, N번째 줄까지 각 줄에 1~9번까지 타자의 타석 결과가 주어짐 

▶ Output : 최대로 얻을 수 있는 점수 출력

---

◈ Input - 1

2
0 4 4 4 4 4 4 4 4
0 4 4 4 4 4 4 4 4

◈ Output - 1

43

◈ Input - 2

2
4 3 2 1 0 4 3 2 1
1 2 3 4 1 2 3 4 0

◈ Output - 2

46

◈ Input - 3

9
1 2 4 3 0 2 1 0 3
1 2 1 2 0 0 0 0 1
3 4 2 3 1 2 3 4 0
0 1 2 3 4 2 1 0 0
0 0 0 0 0 0 1 4 4
0 4 0 4 0 4 0 4 0
0 4 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 0
0 2 0 3 0 1 0 2 0

◈ Output - 3

89

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 재귀 형태의 완전 탐색 시도

▶ 0~8까지 중복되지 않도록 모든 가능한 순서를 배치하여 저장 (1~9번타자 배치) ( 백준 N과M (1)과 로직 동일)

▶ 이 때, 0번 선수는 반드시 3번 인덱스에 저장 ( 1번 선수는 반드시 4번타자로 지정 )

▶ ArrayList의 제네릭을 int형 1차원 배열로 받아서 2차원 자료구조 형태로 배치 가능한 모든 경우의 수 저장

▶ 각 타자의 타격을 표현하기 위해 boolean형 배열을 선언, 안타,2루타,3루타, 홈런을 주자 상태 확인하여 점수 카운트

    => 안타 : 베이스의 모든 주자가 1루씩 전진 후 1루에 타자 배치

    => 2루타 : 베이스의 모든 주자가 2루씩 전진 후 2루에 타자 배치

    => 3루타 : 베이스의 모든 주자가 3루씩 전진 후 3루에 타자 배치

    => 홈런 : 베이스의 모든 주자 수 + 1 만큼 점수 카운트

▶ 아웃 카운트가 3개 될 때 까지 타자의 타격 활동을 반복, 3번 아웃시 이닝 + 1

▶ N개의 이닝이 끝날 때 까지 타자의 타격 활동을 반복, 각 이닝이 끝날 때는 반드시 베이스의 주자 상태 초기화 

▶ 타자 배치가 가능한 모든 경우의 수를 탐색하여 최대값 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, nMax, nHitter;
	static int[] narrTemp;
	static boolean[] barrNumVisit;
	static boolean[] barrBase;
	static ArrayList<int[]> arrHitterList;
	static int[][] narrInning;

	public static void main(String[] args) throws IOException {
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(bReader.readLine());

		narrInning = new int[N][9];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < 9; j++) {
				narrInning[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		narrTemp = new int[9];
		barrNumVisit = new boolean[9];
		barrBase = new boolean[3];
		arrHitterList = new ArrayList<>();

		SetHitter(0);
		nMax = 0;
		
		for(int i = 0; i < arrHitterList.size(); i++) {
			// 타자 배치 경우의수
			// 게임 셋
			int nScore = 0;
			nHitter = 0;
			
			for(int j = 0; j < N; j++) {
				int nOutCount = 0;
				// 각 이닝 별 가능한 타자들의 안타
				// 베이스 초기화
				barrBase = new boolean[3];
				while(nOutCount < 3){
					int nHit = narrInning[j][arrHitterList.get(i)[nHitter]];
					// 아웃 됬으면 ?
					if(nHit == 0)
						nOutCount++;
					else {
						// 노아웃 안타~홈런까지! 인생 역전!
						nScore += Hit(nHit);
					}
					nHitter++;
					// 0~8까지 인덱스 값만 존재 (1~9번 타자)
					if(nHitter > 8)
						nHitter = 0;
				}
			}
			
			if(nMax < nScore)
				nMax = nScore;
		}
		
		bWriter.write(String.valueOf(nMax));
		bWriter.close();

	}

	private static void SetHitter(int nIndex) {
		// 기저 조건
		// Index 0~8번까지 모든 타자 번호가 배치가 완료 되었다안
		if (nIndex == 9) {
			// 깊은 복사 하지 않으면 배열의 메모리가 공유됩니다.
			int[] narrBuffer = new int[9];

			for (int i = 0; i < 9; i++)
				narrBuffer[i] = narrTemp[i];

			arrHitterList.add(narrBuffer);
			return;
		}

		// 4번타자는 무조건 1번 선수이다. 인덱스로는 0
		if (nIndex == 3) {
			narrTemp[nIndex] = 0;
			SetHitter(nIndex + 1);
		}

		// 재귀 조건
		for (int i = 1; i < 9; i++) {
			if (!barrNumVisit[i]) {
				barrNumVisit[i] = true;
				narrTemp[nIndex] = i;
				SetHitter(nIndex + 1);
				barrNumVisit[i] = false;
			}
		}
	}


	private static int Hit(int nNum) {
		int nScore = 0;
		// 홈런쳤다.
		if (nNum == 4) {
			nScore++;
			for (int i = 0; i < 3; i++) {
				if (barrBase[i]) {
					nScore++;
					barrBase[i] = false;
				}
			}
		}
		// 안타 쳤다
		if (nNum == 1) {
			if (barrBase[2]) {
				nScore++;
				barrBase[2] = false;
			}
			
			for(int i = 1; i >=0 ;i--) {
				if(barrBase[i]) {
					barrBase[i+1] = true;
					barrBase[i] = false;
				}
			}
			
			barrBase[0] = true;
		}
		// 2루타 쳤다
		if (nNum == 2) {
			for (int i = 1; i < 3; i++) {
				if (barrBase[i]) {
					barrBase[i] = false;
					nScore++;
				}
			}
			if (barrBase[0]) {
				barrBase[2] = true;
				barrBase[0] = false;
			}
			barrBase[1] = true;
		}
		// 3루타 쳤다.
		if (nNum == 3) {
			for (int i = 0; i < 3; i++) {
				if (barrBase[i]) {
					barrBase[i] = false;
					nScore++;
				}
			}
			barrBase[2] = true;
		}
		
		return nScore;
	}

}

---

Good Luck! (피드백 감사합니다!)