백준 17281번: 야구⚾

문제 설명

• N이닝동안 야구가 진행됩니다.
• 해당 선수가 N이닝에 칠 수 있는 타수가 주어집니다.
• 한번 정해진 순서는 바꿀 수 없습니다.
• 1번선수는 항상 4번째로 순서가 고정되어 있습니다.
• 아웃을 3번 당하면 이닝이 끝납니다.

접근법

• 완전탐색으로 문제를 해결할 수 있습니다.
  • 9개의 숫자를 한줄로 세우는 경우의 수는 9!(362880)으로 제한시간 이내에 풀이가 가능합니다.
• 9명의 선수를 배치하는 모든 가능한 경우의 수를 구합니다.
• 각 경우에 대해 직접 야구를 플레이해 점수를 구하고, 그 중 가장 큰 점수를 최종 정답으로 출력합니다.

정답

import java.util.*;

public class Main {
	static int[] permu_answer = new int[9];
	static boolean[] v = new boolean[9];
	static int max_score = 0;
	static int player = 0;
	static int N;
	static int[][] hit_array;

	public static void main(String[] args) {
		// 입력값 세팅
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		hit_array = new int[N][9]; // 각 선수들이 칠 수 있는 타수의 정보를 담은 배열입니다.
		// hit_array[i][j]는 j번째 선수가 i이닝에 칠 수 있는 타수를 의미합니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 9; j++) {
				hit_array[i][j] = sc.nextInt();
			}
		}
		permu(0);
		System.out.println(max_score);

	}

	// 야구의 규칙을 구현합니다.
	public static int playball(int[] round_array) { // round_array는 이번 이닝에 선수들이 칠 수 있는 타수의 정보입니다.
		int out_cnt = 0;
		int score = 0;
		int[] base = new int[3]; // 1루,2루,3루에 사람이 있는지에 대한 정보를 담고 있습니다. 사람이 있으면 1, 사람이 없으면 0입니다.
		while (out_cnt < 3) { // 3아웃 전까지 계속 플레이 합니다.
			int hit = round_array[player]; // hit는 player번째 선수가 칠 수 있는 타수 입니다.
			if (hit == 1) { // 안타를 쳤을 때
				score += base[2]; // 3루에 사람이 있다면 점수가 1점 추가됩니다.
				// 2루에 있는 사람은 3루로 이동합니다.
				int temp1 = base[1];
				base[2] = temp1;
				// 1루에 있는 사람은 2루로 이동합니다.
				int temp0 = base[0];
				base[1] = temp0;
				// 안타를 친 선수가 1루로 이동합니다.
				base[0] = 1;
			}
			if (hit == 2) { // 2루타를 쳤을 때
				score += (base[2] + base[1]); // 3루,2루에 있는 사람만큼 점수가 추가됩니다.
				int temp0 = base[0];
				base[2] = temp0; // 1루에 있던 선수가 3루로 이동합니다.
				base[1] = 1; // 2루타를 친 선수가 2루로 이동합니다.
				base[0] = 0; // 1루에는 아무도 없습니다.
			}
			if (hit == 3) { // 3루타를 쳤을 때
				score += (base[2] + base[1] + base[0]); // 3루,2루,1루에 있는 사람만큼 점수가 추가됩니다.
				Arrays.fill(base, 0); // 1루와 2루에는 아무도 없습니다.
				base[2] = 1; // 3루타를 친 선수가 3루로 이동합니다.
			}
			if (hit == 4) { // 홈런을 쳤을 때
				score += (1 + base[2] + base[1] + base[0]);
				Arrays.fill(base, 0); // 모두 홈으로 들어오기 때문에 아무도 남아있지 않습니다.
			}
			if (hit == 0) { // 아웃을 당하면
				out_cnt++; // 아웃카운트가 증가합니다.
			}
			player = (player + 1) % 9; // 9명의 선수가 계속해서 반복합니다.
		}
		return score;
	}

	public static void permu(int depth) {
		if (depth == 9) {
			// 완성된 순서를 가지고 야구를 진행합니다.
			int score = 0;
			for (int i = 0; i < N; i++) { // N이닝 진행합니다.
				int[] round_array = new int[9]; // i이닝에서 선수들의 타수입니다.
				for (int j = 0; j < 9; j++) {
					round_array[j] = hit_array[i][permu_answer[j]]; // [i] -> i이닝, [permu_answer[j]] -> j번째 순서에  permu_answer[j]선수를 쓰겠다는 뜻
				}
				score += playball(round_array); // 이닝이 끝날 때마다 점수를 더합니다.
			}
			player = 0;
			max_score = Math.max(max_score, score);
			return;
		}
		for (int i = 0; i < 9; i++) {
			// i를 이미 사용했다면 continue -> 기존 순열을 만드는 조건
			// (depth == 3 && i != 0) -> 첫번째 선수가 4번타자여야 한다는 이번 문제의 조건
			if (v[i] || (depth == 3 && i != 0)) continue;
			v[i] = true;
			permu_answer[depth] = i;
			permu(depth + 1);
			v[i] = false;

		}
	}
}

기타

• 이번에도 완전탐색인지 몰랐다. 완전탐색의 가능성을 언제나 생각하자!!
• 처음에 Arrays.fill을 통해 0으로 초기화하는 과정을 안넣어서 틀린 정답이 나왔다.