[Gold IV] ⚾ - 17281
성능 요약
메모리: 295764 KB, 시간: 908 ms
분류
브루트포스 알고리즘(bruteforcing), 구현(implementation)
문제 설명
⚾는 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
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
출력
아인타팀이 얻을 수 있는 최대 점수를 출력한다.
풀이
순열을 활용해서 타자들의 순서를 정하고,
그대로 게임을 한 후 최대값을 찾으면 된다.
시간 초과때문에 여러번 수정을 거쳤다.
처음에는 타자들의 순서를 Queue에 넣어 하나씩 빼고 다시 offer하는 식으로 하였는데, 그냥 배열의 index로 순환하는 것으로 수정하였다.
그리고 진루하는 과정에서 홈런을 친 경우에는 필드에 있는 모든 타자가 홈으로 돌아오는 것이니까 하나씩 더해주지 않고 field에 있는 타자의 수 만큼 점수에 더하였다. 이 과정에서 시간을 단축할 수 있었다.
1. 순열
1번 선수는 4번으로 순서가 고정되어 있기 때문에 순열을 구할 때 3번 index는 바로 다음으로 넘어가도록 하였다.
static void perm(int depth) {
if (depth == 9) {
game();
return;
}
if (depth == 3) {
perm(depth + 1);
return;
}
for (int i = 0; i < 9; i++) {
if (!visited[i]) {
order[depth] = i;
visited[i] = true;
perm(depth + 1);
visited[i] = false;
}
}
}
2. 게임
한 이닝은 아웃이 3번 나오면 종료된다.
그래서 이닝의 수(gameCnt), 아웃의 수(out), 점수(score), 현재 주자(curr)로 변수를 선언하고, 진루하여 필드에 있는 선수들을 리스트에 저장하였다.
선수는 계속해서 순환하기 때문에 다음 선수는 (curr+1%9)로 정의하였다.
결과값이 0이면 아웃을 증가시키고, 0이 아닐 경우에는 선수들이 진루하도록 구현하였다.
static void game() {
int out = 0;
int gameCnt = 0;
int score = 0;
int curr = 0;
List<int[]> field = new LinkedList<>();
while (gameCnt < N) {
int player = order[curr];
curr = (curr + 1) % 9;
int result = arr[gameCnt][player];
if (result == 0) {
out++;
if (out == 3) {
gameCnt++;
out = 0; // 다음 이닝으로
field.clear(); // 필드 초기화
}
} else {
field.add(new int[] { player, 0 });
if (result == 4) {
score += field.size();
field.clear();
continue;
}
// 필드에 나가있는 선수가 있으면 진루하기
int size = field.size();
for (int i = size - 1; i >= 0; i--) {
int[] tmp = field.get(i);
if (tmp[1] + result >= 4) {
field.remove(tmp);
score++;
} else {
tmp[1] += result;
}
}
}
}
ans = Math.max(ans, score);
}
전체 코드
package BOJ.Gold.g4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ_17281_야구 {
static int N;
static int[][] arr;
static boolean[] visited;
static int[] order;
static int ans = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N][9];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++)
arr[i][j] = Integer.parseInt(st.nextToken());
}
visited = new boolean[9];
order = new int[9];
// 순열
order[3] = 0;
visited[0] = true; // 4번타자로 고정
perm(0);
System.out.println(ans);
// 게임 진행
}
static void perm(int depth) {
if (depth == 9) {
game();
return;
}
if (depth == 3) {
perm(depth + 1);
return;
}
for (int i = 0; i < 9; i++) {
if (!visited[i]) {
order[depth] = i;
visited[i] = true;
perm(depth + 1);
visited[i] = false;
}
}
}
static void game() {
int out = 0;
int gameCnt = 0;
int score = 0;
int curr = 0;
List<int[]> field = new LinkedList<>();
while (gameCnt < N) {
int player = order[curr];
curr = (curr + 1) % 9;
int result = arr[gameCnt][player];
if (result == 0) {
out++;
if (out == 3) {
gameCnt++;
out = 0; // 다음 이닝으로
field.clear(); // 필드 초기화
}
} else {
field.add(new int[] { player, 0 });
if (result == 4) {
score += field.size();
field.clear();
continue;
}
// 필드에 나가있는 선수가 있으면 진루하기
int size = field.size();
for (int i = size - 1; i >= 0; i--) {
int[] tmp = field.get(i);
if (tmp[1] + result >= 4) {
field.remove(tmp);
score++;
} else {
tmp[1] += result;
}
}
}
}
ans = Math.max(ans, score);
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 17244 - 아맞다우산 (자바 Java) (0) | 2022.10.21 |
---|---|
[백준] 9466 - 텀 프로젝트 (자바 Java) (0) | 2022.10.17 |
[백준] 17136 - 색종이 붙이기 (자바 Java) (0) | 2022.10.13 |
[백준] 1931 - 회의실 배정 (자바 Java) (0) | 2022.10.12 |
[백준] 2206 - 벽 부수고 이동하기 (자바 Java) (0) | 2022.10.07 |