📚 Problem
📝 Solution
- 1번 ~ 9번까지의 선수들의 타순을 찾아 최대의 득점수 찾기
- 4번 타자 는 1번 선수로 고정
- 타순을 정하는 것이 "순서가 있는 배열하기" 이기 때문에, 순열(Permutation)을 사용
- Permutation 을 구현하기 위해 DFS 를 이용
player : 선수들의 번호를 나타내는 배열
order : DFS를 반복할 때마다 달라지는 순서를 저장하는 배열
visited : 해당 번호의 방문 여부를 저장하는 배열
- 1번 선수는 4번 타자로 고정이기 때문에, order[4]에 1을 넣습니다
order[4] = player[1]; // batter number 4 is one;
visited[1] = true;- 1번 선수를 제외한 2~9번 선수들의 방문 여부를 확인하여 "순서가 있는 배열하기"를 진행합니다
for(int i = 2; i <= 9; i++){
if(!visited[i]){
visited[i] = true;
if(depth != 4)
order[depth] = player[i];
DFS(depth + 1);
visited[i] = false;
}
}- 종료조건인 depth==9 일때,
order[9]에 아무런 값이 들어가지 않아 1에서 9까지 모두 더한 45 에서
이미 순서가 정해진 order[1] ~ order[8] 의 선수들의 번호를 빼주면
order[9]의 값을 알 수 있게 됩니다
if(depth == 9){
int temp = 45;
for(int i = 1; i <= 8; i++)
temp -= order[i];
order[depth] = temp;
max = Math.max(max, baseball());
return;
}- 일반 야구의 규칙으로 switch문을 사용해 N 이닝 만큼 야구를 진행합니다
private static int baseball(){
int score = 0, temp = 1, inningTemp = 1, outTemp = 0;
boolean[] base = new boolean[3];
while (inningTemp <= N){
switch (innings[inningTemp][order[temp]]){
case 0:
outTemp++;
break;
case 1:
if(base[2]){
score++;
base[2] = false;
}
if(base[1]){
base[2] = true;
base[1] = false;
}
if(base[0]){
base[1] = true;
base[0] = false;
}
base[0] = true;
break;
case 2:
if(base[2]){
score++;
base[2] = false;
}
if(base[1]){
score++;
base[1] = false;
}
if(base[0]){
base[2] = true;
base[0] = false;
}
base[1] = true;
break;
case 3:
for(int i = 0; i < 3; i++)
if(base[i]){
score++;
base[i] = false;
}
base[2] = true;
break;
case 4:
for(int i = 0; i < 3; i++)
if(base[i]){
score++;
base[i] = false;
}
score++;
break;
}
if(outTemp == 3){
inningTemp++;
outTemp = 0;
for(int i = 0; i < 3; i++)
base[i] = false;
}
temp = (temp % 9) + 1;
}
return score;
}- 한 이닝을 진행하면서 만약 3아웃이 됐다면, 현재 진행중인 이닝의 크기에 +1을 해주고 out을 초기화해주고 베이스들을 비워 줍니다
if(outTemp == 3){
inningTemp++;
outTemp = 0;
for(int i = 0; i < 3; i++)
base[i] = false;
}- 다음 이닝으로 넘어가면 순서가 1번부터 시작이 아닌, 이전 이닝의 진행했던 타순 다음부터 이어 가기 때문에 1~9사이의 번호를 이어서 저장합니다
temp = (temp % 9) + 1;💻 Code
import java.util.Scanner;
public class Main {
private static int N, max;
private static int[] player = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
private static int[] order = new int[10];
private static boolean[] visited = new boolean[10];
private static int[][] innings;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
innings = new int[N + 1][10];
for(int i = 1; i <= N; i++)
for(int j = 1; j <= 9; j++)
innings[i][j] = scanner.nextInt();
order[4] = player[1]; // batter number 4 is one;
visited[1] = true;
DFS(1);
System.out.println(max);
scanner.close();
}
private static int baseball(){
int score = 0, temp = 1, inningTemp = 1, outTemp = 0;
boolean[] base = new boolean[3];
while (inningTemp <= N){
switch (innings[inningTemp][order[temp]]){
case 0:
outTemp++;
break;
case 1:
if(base[2]){
score++;
base[2] = false;
}
if(base[1]){
base[2] = true;
base[1] = false;
}
if(base[0]){
base[1] = true;
base[0] = false;
}
base[0] = true;
break;
case 2:
if(base[2]){
score++;
base[2] = false;
}
if(base[1]){
score++;
base[1] = false;
}
if(base[0]){
base[2] = true;
base[0] = false;
}
base[1] = true;
break;
case 3:
for(int i = 0; i < 3; i++)
if(base[i]){
score++;
base[i] = false;
}
base[2] = true;
break;
case 4:
for(int i = 0; i < 3; i++)
if(base[i]){
score++;
base[i] = false;
}
score++;
break;
}
if(outTemp == 3){
inningTemp++;
outTemp = 0;
for(int i = 0; i < 3; i++)
base[i] = false;
}
temp = (temp % 9) + 1;
}
return score;
}
private static void DFS(int depth){
if(depth == 9){
int temp = 45;
for(int i = 1; i <= 8; i++)
temp -= order[i];
order[depth] = temp;
max = Math.max(max, baseball());
return;
}
for(int i = 2; i <= 9; i++){
if(!visited[i]){
visited[i] = true;
if(depth != 4)
order[depth] = player[i];
DFS(depth + 1);
visited[i] = false;
}
}
}
}
New, Strange, Want to try