Java/BOJ
[BOJ] 백준 17281. 야구
동구름이
2024. 4. 2. 15:44
문제
https://www.acmicpc.net/problem/17281
17281번: ⚾
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종
www.acmicpc.net
풀이
순열이 포함된 구현 문제입니다.
처음에는, 점수를 계산하는 과정을 큐로 구현을 했습니다. Base를 돌고 홈으로 오는 선수들을 큐 자료형을 표현했는데 시간 초과가 나서, 점수를 산정하는 과정을 boolean[] 배열을 통해 경우를 따져가는 식으로 변경했습니다.
그리고 순열 시에 1번 타자는 항상 4번 째에 위치하는 것을 고려해, 해당 depth일 때는 배정을 한 칸씩 뒤로 미루었습니다.
아래는 소스 코드와, 추가로 큐로 구현했던 코드(시간 초과남) 입니다.
소스 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
static int N;
static int maxScore = -5;
static int score;
static int[][] players;
static int[] orders = new int[9];
static boolean[] visited = new boolean[9];
public static void main(String[] args) {
input();
setOrder(0);
System.out.println(maxScore);
}
static void input(){
N = sc.nextInt();
players = new int[N][9];
for(int i =0;i<N;i++){
for(int j=0;j<9;j++){
players[i][j] = sc.nextInt();
}
}
}
static void setOrder(int depth){
if(depth == 8){
playGame(orders);
maxScore = Math.max(maxScore,score);
}
else {
for (int i = 1; i < 9; i++) {
if (!visited[i]) {
visited[i] = true;
if(depth>=3) orders[depth+1] = i;
else orders[depth] = i;
setOrder(depth + 1);
visited[i] = false;
}
}
}
}
static void playGame(int[] order){
int inning = 0;
int nowNum = 0;
score = 0;
for(int r=0; r<N; r++) {
int inningScore = 0;
int outCnt = 0;
boolean[] base = new boolean[4];
while(outCnt < 3) {
switch(players[r][order[nowNum]]) {
case 0:
outCnt++;
break;
case 1:
if(base[3]) {
inningScore++;
base[3] = false;
}
if(base[2]) {
base[3] = true;
base[2] = false;
}
if(base[1]) {
base[2] = true;
}
base[1] = true;
break;
case 2:
if(base[3]) {
inningScore++;
base[3] = false;
}
if(base[2]) {
inningScore++;
}
if(base[1]) {
base[3] = true;
base[1] = false;
}
base[2] = true;
break;
case 3:
if(base[3]) {
inningScore++;
}
if(base[2]) {
inningScore++;
base[2] = false;
}
if(base[1]) {
inningScore++;
base[1] = false;
}
base[3] = true;
break;
case 4:
if(base[3]) {
inningScore++;
base[3] = false;
}
if(base[2]) {
inningScore++;
base[2] = false;
}
if(base[1]) {
inningScore++;
base[1] = false;
}
inningScore++;
break;
}
nowNum++;
if(nowNum > 8) {
nowNum = 0;
}
}
score += inningScore;
}
}
}
시간 초과 코드 참고 (Queue)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
static int N;
static int maxScore = -5;
static int[][] players;
static int[] orders = new int[9];
static boolean[] visited = new boolean[9];
public static void main(String[] args) {
input();
setOrder(0);
System.out.println(maxScore);
}
static void input(){
N = sc.nextInt();
players = new int[N][9];
for(int i =0;i<N;i++){
for(int j=0;j<9;j++){
players[i][j] = sc.nextInt();
}
}
}
static void setOrder(int depth){
if(depth == 8){
playGame(orders);
}
else {
for (int i = 1; i < 9; i++) {
if (!visited[i]) {
visited[i] = true;
if(depth>=3) orders[depth+1] = i;
else orders[depth] = i;
setOrder(depth + 1);
visited[i] = false;
}
}
}
}
static void playGame(int[] order){
int inning = 0;
int nowNum = 0;
int score = 0;
int outCnt = 0;
Queue<Integer> base = new LinkedList<>();
while(inning<N){
int playerNum = order[nowNum];
int ru = players[inning][playerNum];
if(ru!=0){
base.add(1);
for(int r= 1;r<ru;r++){
base.add(0);
}
while (base.size() > 3) {
if (base.poll() == 1) score++;
}
}
else outCnt++;
nowNum++;
if(nowNum>8) nowNum=0;
if(outCnt==3) {
outCnt=0;
inning++;
base = new LinkedList<>();
}
}
maxScore = Math.max(maxScore,score);
}
}