BOJ 17281
위 문제는 백준 사이트의 알고리즘 17281 문제에 관한 설명입니다.
문제
⚾는 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
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
출력
아인타팀이 얻을 수 있는 최대 점수를 출력한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][] game;
static boolean[] visit;
static int[] player;
static int max;
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine()); // 이닝
game = new int[N][10];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine());
for (int j = 1; j < 10; j++) { // 이닝별 점수? 를 기록하자
game[i][j] = Integer.parseInt(st.nextToken());
}
}
visit = new boolean[10];
player = new int[10]; // 플레이어는 10명
player[4] = 1;// 4번타자는 1번이다.
max = 0; //
perm(1);// 1번부터 permutation
System.out.println(max);
}// end of main
public static void perm(int num) { // 선수 배치하기
if (num == 4) { // 4번째 타자는 1번.
perm(num + 1);
return;
}
if (num == 10) { // 선택완료
int score = playGame();
if (max < score)
max = score;
return;
}
for (int i = 2; i < 10; i++) { // 1번은 선택되었으니 나머지를 고른다.
if (visit[i])// 뽑았다.
continue;
player[num] = i; // 해당번째 타자는 i야.
visit[i] = true;// 뽑고.
perm(num + 1);
visit[i] = false;// 안뽑고
}
}
public static int playGame() {
int score = 0;// 게임의 시작은 0 점에서 시작한다.
int out;
boolean[] base = new boolean[4]; // 4군데의 베이스가 있음/
int taza = 1; // 타자는 1번
for (int inning = 0; inning < N; inning++) {// 이닝을 하나씩 실행한다.
out = 0; // 이닝의 시작을 위해 아웃을 0으로 세팅, 베이스를 비우자.
Arrays.fill(base, false);
while (true) {
int ball = game[inning][player[taza]];
taza++;
if (taza == 10)
taza = 1;
if (ball == 1) { // 안타
if (base[3]) {
score++;
base[3] = false;
}
for (int i = 2; i >= 1; i--) {
if (base[i]) {
base[i] = false;
base[i + 1] = true;
}
}
base[1] = true;
} else if (ball == 2) { // 2루타
if (base[3]) {
score++;
base[3] = false;
}
if (base[2]) {
score++;
base[2] = false;
}
if (base[1]) {
base[1] = false;
base[3] = true;
}
base[2] = true;
} else if (ball == 3) { // 3루타
for (int i = 1; i <= 3; i++) {
if (base[i]) {
score++;
base[i] = false;
}
}
base[3] = true;
} else if (ball == 4) {
for (int i = 1; i <= 3; i++) {
if (base[i]) {
score++;
base[i] = false;
}
}
score++;
} else if (ball == 0) {
out++;
if (out == 3) {
break;
}
}
}
}
return score;
}
}
이번 문제는 순열과 시뮬레이션을 사용했습니다.
//입력부 입니다.
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine()); // 이닝
game = new int[N][10];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine());
for (int j = 1; j < 10; j++) { // 이닝별 점수? 를 기록하자
game[i][j] = Integer.parseInt(st.nextToken());
}
}
visit = new boolean[10];
player = new int[10]; // 플레이어는 10명
player[4] = 1;// 4번타자는 1번이다.
max = 0; //
perm(1);// 1번부터 permutation
System.out.println(max);
}
각 이닝별 점수를 game[][]에 기록해두고
visit[]을 이용해 선발되는 인원을 뽑았는지 안뽑았는지를 확인합니다.
`player[]’에는 몇번째 타자로 몇번이 들어가는가를 정합니다.
이제 순서를 정해서 뽑아야하니 순열을 사용해서 인원들을 뽑습니다.
public static void perm(int num) { // 선수 배치하기
if (num == 4) { // 4번째 타자는 1번.
perm(num + 1);
return;
}
if (num == 10) { // 선택완료
int score = playGame();
if (max < score)
max = score;
return;
}
for (int i = 2; i < 10; i++) { // 1번은 선택되었으니 나머지를 고른다.
if (visit[i])// 뽑았다.
continue;
player[num] = i; // 해당번째 타자는 i야.
visit[i] = true;// 뽑고.
perm(num + 1);
visit[i] = false;// 안뽑고
}
}
순열부입니다.
가장 좋아하는 1번선수는 4번타자로 정합니다.
4번이 아닌경우 2~9번 선수를 고르고, 안고르고를 정하면서 순열을 돌립니다.
깊이가 10으로 선발되는 선수들이 정해졌을 때 playGame()함수를 실행합니다.
함수가 다 돌아간다면 반환되는 점수의 값을 여태껏 저장했던 점수들 중
가장 큰 max와 비교해 더 큰 값을 넣어줍니다.
public static int playGame() {
int score = 0;// 게임의 시작은 0 점에서 시작한다.
int out;
boolean[] base = new boolean[4]; // 4군데의 베이스가 있음/
int taza = 1; // 타자는 1번
for (int inning = 0; inning < N; inning++) {// 이닝을 하나씩 실행한다.
out = 0; // 이닝의 시작을 위해 아웃을 0으로 세팅, 베이스를 비우자.
Arrays.fill(base, false);
while (true) {
int ball = game[inning][player[taza]];
taza++;
if (taza == 10)
taza = 1;
if (ball == 1) { // 안타
if (base[3]) {
score++;
base[3] = false;
}
for (int i = 2; i >= 1; i--) {
if (base[i]) {
base[i] = false;
base[i + 1] = true;
}
}
base[1] = true;
} else if (ball == 2) { // 2루타
if (base[3]) {
score++;
base[3] = false;
}
if (base[2]) {
score++;
base[2] = false;
}
if (base[1]) {
base[1] = false;
base[3] = true;
}
base[2] = true;
} else if (ball == 3) { // 3루타
for (int i = 1; i <= 3; i++) {
if (base[i]) {
score++;
base[i] = false;
}
}
base[3] = true;
} else if (ball == 4) {
for (int i = 1; i <= 3; i++) {
if (base[i]) {
score++;
base[i] = false;
}
}
score++;
} else if (ball == 0) {
out++;
if (out == 3) {
break;
}
}
}
}
return score;
}
점수는 게임 시작시 0 점부터 시작을하고, 4군데의 베이스가 있습니다.
각 이닝시작시 야구의 룰 처럼 아웃은 0으로 초기화 해주고,
4곳의 베이스에서는 아무도 없는 것으로 초기화 해줍니다.
선택된 N번쨰 타자들은 순서대로 돌아가면서 진행을 하게되고,
안타 시 1베이스 씩, 2루타 시 2베이스 씩, 3루타시 3베이스 씩, 확인을 합니다.
만약 홈런이라면 베이스 별로 있는 사람들의 값을 스코어로 올리고, 타자 본인까지 포함해서 늘려줍니다.
아웃이라면 아웃 카운트를 하는 out 변수를 하나씩 늘려주고, 3아웃이면 이닝을 끝냅니다.