"⚾" - 17281번 G4

🎃문제설명

⚾는 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

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

출력

아인타팀이 얻을 수 있는 최대 점수를 출력한다.

💾입출력 예

입력	출력
2 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0	1
2 4 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0	4
2 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4	43
2 4 3 2 1 0 4 3 2 1 1 2 3 4 1 2 3 4 0	46
9 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4 0	216
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	89

알고리즘 분류

• 구현
• 브루트포스 알고리즘

강의내용

✔️게임을 시작하기 전에 타순을 모두 결정한다. (단, 1번선수는 4번타자로 고정)
    => 8!
✔️시간복잡도 : (게임 플레이) N x (1이닝당) x 3아웃 x 9명 선수
    => 8! x N(최대 50) x 3 x 9 = 54432000

🌟문제 이해 및 풀이계획

✏️1번 선수(4번 타자로 고정) 제외하고 나머지 8명의 순서를 순열로 모두 구하고, 각 순서에 대해 플레이 후 최대값을 뽑는다.

✍🏻내 코드1 - 오답코드

package BOJ;

import java.util.Arrays;
import java.util.Scanner;

public class boj_17281 {
	
	static int n, max = 0;
	static int[][] inning;
	static boolean[] visited = new boolean[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		inning = new int[n][9];
		for(int i=0; i<n; i++) {
			for(int j=0; j<9; j++) {
				inning[i][j] = sc.nextInt();
			}
		}
		sc.close();
		
		// 타자 순서를 고려하지 않은 플레이 - 오류코드
		for(int i=0; i<n; i++) {
			if(out >= 3) break;
			while(true) {
				if(idx >= 9) idx = 0;
				// 유효타일 때
				if(inning[i][idx] != 0) {
					for(int k=3; k>=1; k--) {
						if(base[k] > 0) {
							base[k] = 0;
							if(k + inning[i][idx] > 3) score += 1;
							else {
								base[k+inning[i][idx]] = 1;
							}
						}
					}
					if(inning[i][idx] == 4) score += 1;
					else base[inning[i][idx]] = 1;
					idx += 1;
				}
				// 아웃일 때
				else {
					idx += 1;
					out += 1;
					break;
				}
			}
		}
		
		System.out.println(max);
	}
	
}

❌처음에는 순서에 대한 고려를 전혀 하지 않고 그냥 순서대로 게임을 진행했다. 게임 플레이 전, 팀의 순서를 미리 정해야 한다.

⚔️순열을 이용하여 모든 순서를 구한 뒤, 게임을 진행하고 플레이 중 제일 큰 점수를 저장한다.

⚔️order()함수를 이용하여 순열로 선수의 모든 순서를 구해 runners[]배열에 저장한다.(4번타자 1번선수로 고정)

⚔️runners[]배열을 이용하여 타순을 정한다. (4번타자 1번선수로 고정)

⚔️유효타와 아웃일 때를 구분하여 타자의 순서는 유지한 채 base[]배열을 이용하여 각 1루,2루,3루에 주자가 있는지 검사하고 안타 수에 따라 얻는 점수를 계산해준다.

✍🏻내 코드2 + 강의

package BOJ;

import java.util.Arrays;
import java.util.Scanner;

/*
 * 2021.01.18 daily algo/commit
 * 
 * Brute Force
 * 문제에 대한 기본적인 이해!
 * - 한 이닝은 3아웃이 되기 전까지 반복된다.
 * - 3아웃 시 주자는 초기화된다.
 * - 다음 이닝으로 넘어갈 때 타자의 순서는 유지된다.
 */

public class boj_17281 {
	
	static int n, max = 0;
	static int[][] inning;
	static int[] runners;
	static boolean[] visited = new boolean[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		inning = new int[n][9];
		for(int i=0; i<n; i++) {
			for(int j=0; j<9; j++) {
				inning[i][j] = sc.nextInt();
			}
		}
		sc.close();
		
		runners = new int[10]; // 현재 타자 순서
		runners[4] = 1; // 4번타자는 무조건 1번선수
		order(9, 1, 2, runners);
		
		System.out.println(max);
	}
	
	// 선수 순서 정하기
	public static void order(int n, int r, int start, int[] runners) {
		if(r == 9) {
			max = Math.max(max, play(runners));
			return;
		}
		for(int i=2; i<=9; i++) {
			if(!visited[i]) {
				visited[i] = true;
				if(r >= 4) {
					runners[r+1] = i;
				}
				else runners[r] = i;
				order(n, r+1, i+1, runners);
				visited[i] = false;
			}
		}
	}

	public static int play(int[] runners) {
		int idx = 1; // 순서
		int[] base = new int[4]; // 현재 베이스에 있는 선수
		base[0] = 1;
		int out = 0; // 아웃 수
		int score = 0; // 현재 점수
		
		for(int i=0; i<n; i++) {
			while(true) {
				if(idx > 9) idx = 1;
				// 유효타일 때
				if(inning[i][runners[idx]-1] != 0) {
					int hits = inning[i][runners[idx]-1];
					for(int k=3; k>=0; k--) {
						if(k + hits > 3) {
							score += base[k];
						}
						else base[k + hits] = base[k];
						if(k == 0) base[k] = 1;
						else base[k] = 0;
					}
					idx += 1;
				}
				// 아웃일 때
				else {
					idx += 1;
					out += 1;
					if(out >= 3) {
						out = 0; // 아웃 횟수 초기화
						Arrays.fill(base, 0);
						base[0] = 1;
						break;
					}
				}
			}
		}
		return score;
	}
}

💡base[]배열을 이용하여 안타 점수에 따라 점수를 계산하는 것이 헷깔렸다. 3 -> 2 -> 1루 순으로 주자가 있는지 없는지를 검사하고 주자가 있으면 1, 없으면 0으로 표현하는 과정에서 주자가 홈을 통과해 점수를 얻는 경우와 홈을 통과하지 못해 베이스에 남아있는 경우를 나누었다.
이 때, 주자가 움직이면 그 전을 0으로 만들어주는 로직을 두 경우 모두 짜주어야 했는데 한 경우만 해당하게 해서 시간을 많이 낭비했다.. ㅠ.ㅠ
디버깅을 한참을 해보고 나서야 왜 점수가 제대로 찍히지 않았는지 알아챘다..

💡문제에 대한 이해가 아직도 한참 부족한 것 같다! 빠르게 문제를 접근하는 것 보다 천천히 문제 속의 규칙을 완벽히 파악한 후에 접근하는 습관을 들이자.