Baekjoon[17281] - ⚾

링크

17281번: ⚾

문제설명

• 완전탐색 + 시뮬레이션

문제풀이

• 완전탐색 + 시뮬레이션

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main17281 {

    public static int Ans = Integer.MIN_VALUE;
    public static int Temp;
    public static int N;
    public static int[][] hit;
    public static int[] serial = new int[9];
    public static boolean[] map = new boolean[4];

    public static void score() {
        Temp=0;
        int inning=0;
        int out=0;
        int s_idx=0;    //serial idx
        int h_idx=0;    //hit idx
        int now_hit=0;
        while(inning<N) {
//            한 이닝
            for (int i = 0; i < 4; i++) {
                map[i]=false;
            }
            while(out<3) {
                h_idx = serial[s_idx];
                now_hit = hit[inning][h_idx];
                if(now_hit==0) {
                    out++;
                }
                else {
                    for (int i = 3; i >= 0; i--) {
                        if(map[i]==true) {
                            if(i+now_hit>=4) {
                                Temp++;
                                map[i]=false;
                            }
                            else {
                                map[i]=false;
                                map[i+now_hit]=true;
                            }
                        }
                    }
                    if(now_hit>=4) {
                        Temp++;
                    }
                    else {
                        map[now_hit]=true;
                    }
                }
                s_idx = (s_idx+1)%9;
            }
            out=0;
            inning++;
        }
    }


    public static void Search(int cnt, int flag) {
        if(cnt==9){
//            생성된 타자 순서를 기준으로 점수를 냄
//            System.out.println(Arrays.toString(serial));
            score();
            Ans = Math.max(Ans, Temp);
            return;
        }

//        4번타자는 1번선수이다
        if(cnt==3) {
            Search(cnt+1,flag);
        }
        else {
            for (int i = 1; i < 9; i++) {
//            안겹치면
                if((flag & 1<<i)==0) {
                    serial[cnt]=i;
                    Search(cnt+1,flag|1<<i);
                }
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/baekjoon/17281.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        hit = new int[N][9];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                hit[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Search(0,0);

        System.out.println(Ans);
//        초기화
        Ans=Integer.MIN_VALUE;
    }
}

아쉬운점

• while 조건문 잘못씀 true여야 계속도는거임
  • inning<N임 inning>N가 아니라
• index 실수
  • inning도 0부터 시작임
  • hit 배열 자체를 [0]부터 시작했으니
• LinkedList접근 및 데이터 수정
  • map.set(i, map.get(i)+now_hit); 이건되고
  • map.get(i)+=now_hit; 이건안됨(컴파일에러뜸)
  • 뭔차이지 LinkedList<int[]>일때는 get으로 수정된거같았는데
• 점수계산방법을 1이닝 최대연타수(27회[1이닝최소 1아웃임])^2 만큼 연산하는 알고리즘으로 계산했더니 터졌음
• O(N) 고려했어야했음...
  • 점수계산방법이 27인경우
  • 8!(선수나열조합) * 9이닝 * 최대연타수 * 점수계산(최대연타수) = 8! * 9 * 27 * 27 = 264,539,520‬ = 2.6 * 10^8 애매하긴하다.
    • 3아웃당할때까지 히트친기록을 list에 add하고 그 다음타자가 히트한 만큼 누적시켜서 4이상인경우(홈으로 옴)를 scoring하는 방식
  • 점수계산방법이 4인경우
  • 8!(선수나열조합) * 9이닝 * 최대연타수 * 점수계산(4루) = 8! * 9 * 27 * 4 = 39,191,040 = 4*10^7
    • 4루에 선수들 배치시키면서 4루 나가는경우 scoring하는 방식

점수계산방법에 따른 시간

• 위에서부터 차례로 LinkedList[4루 배치], BooleanArray[4루 배치], LinkedList[최대연타수 고려]
• LinkedList가 메모리 많이 잡아먹는다. 시간도 2배정도차이나고. O(N)으로 따져보면 할만하긴해서 풀리긴했지만 안전하게 풀고싶으면 배열이 좋다.

잘한점

• 점수계산 while문은 깔끔했음
  • inning, out 변수 및 s_idx, h_idx 혼동안하고 했음
  • (s_idx+1)%9 씀
• 1시간 10분
• 점수계산방법을 27(최대연타수) 에서 4(4루)로 줄였음
  • 근데 시간 초과 날거란생각은 못했는데 실전에서 제대로 할 수 있을까