[Java/자바 백준 17281] 공

풀이

 

순열 + 구현 문제인거같다.

 

순열 과정에서 4번째 타자가 1번 선수라는걸 인지하고

백트래킹 시켜줘야하는 문제 ! 안시켜주면 시간초과난다...

 

타자들 순서를 나열하고, 순서대로 게임을 진행하면 되는 문제

처음에 점수 계산 중 1루, 2루, 3루 배열에 넣어서 계산했는데 (이렇게 풀어도 시간 초과 안난다)

 

다른 답안 참고 중 해당 이닝에서 뒤에서부터

다른 합을 구해 4를 넘게 되면 앞에있는 타자들은 모두 득점으로 계산가능하단걸 보고

참고했다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int N, max, temp;
	static boolean[] isSelected;
	static int[][] order;
	static int[] number;
	static List<Integer> list =  new ArrayList<Integer>(); 
	static int[] stadium = new int[3]; 

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		order = new int[N][9];
		isSelected = new boolean[9];
		number = new int[9];
		
		number[3] = 0;
		isSelected[0] = true;
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < 9 ; j++) {
				order[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		permutation(0);
		System.out.println(max);
	}
	private static void permutation(int cnt) {
		if(cnt == 9) {
			gameStart();
			return;
		}
		
		if(cnt == 3) {
			number[cnt] = 0;
			permutation(cnt + 1);
			return;
		}
		
		for(int i = 0 ; i < 9 ; i++) {
			if(isSelected[i]) continue;
			
			number[cnt] = i;
			isSelected[i] = true;
			permutation(cnt + 1);
			isSelected[i] = false;
		}
	}
	private static void gameStart() {
		int outCount = 0;
		int playerIndex = 0;
		int turn = 0;
		temp = 0;
		while(turn < N) {
			int point = order[turn][number[playerIndex++]];
			
			if(point == 0) outCount ++;
			
			else list.add(point);
			
			if(playerIndex == 9) playerIndex = 0;
			
			if(outCount == 3) {
				sumPoint();
				list.clear();
				outCount = 0;
				turn ++;
			}
			
		}
		max = Math.max(temp, max);
	}
	
	private static void sumPoint() {
		int sum = 0;
		for(int i = list.size() - 1 ; i >= 0 ; i--) {
			sum += list.get(i);
			if(sum >= 4) {
				temp += i + 1;
				break;
			}
		}
	}
}