[BOJ] 17281 ⚾ - JAVA

choi-jaewon·2021년 11월 16일
1

Baekjoon Online Judge

목록 보기
4/9

📚 Problem

17281 ⚾

📝 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;
            }
        }
    }
}
profile
New, Strange, Want to try

0개의 댓글