#백준_17281 ⚾ - Java 자바

# 유형 : 탐색+시뮬레이션, DFS, 순열

# 난이도 : 골드 4

# 1번 선수를 4번 타자로 미리 결정하였기 때문에 4번을 1번선수로 고정하고, 나머지 1~3번 5~9번을 순열을 돌려 가장 높은 값을 얻을 때까지 게임을 진행해야 한다. 

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p17281 {
    static int N, maxValue = 0;
    static int arr[][];
    static int check[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][9];
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        check = new int[9];
        
        //좋아하는 선수인 1번 선수를 4번 타자로 미리 결정
        check[3] = 0;
        
        dfs(0);
        System.out.println(maxValue);
        
        
    }
    public static void dfs(int count) {
        if(count == 3) {
            dfs(count+1);
            return;
        }
        
        if(count == 9) {
            int temp = solve();
            maxValue = Math.max(maxValue, temp);
            return;
        }
        
        else {
            for(int n=1; n<9; n++) {
                boolean is = false;
                for(int i=0; i<count; i++) {
                    if(check[i] == n) {
                        is = true;
                        break;
                    }
                }
                
                if(is)
                    continue;
                check[count] = n;
                dfs(count+1);
            }
        }
    }
    private static int solve() {
        
        int result = 0;
        int index = 0;
        
        for(int i=0; i<N; i++) {
            boolean base[] = new boolean[4];
            base[0] = true;
            
            for(int j=0; j<3; j++) {
                int val = arr[i][check[index]];
                if(val == 0) {
                    index++;
                    index%=9;
                }else {
                    for(int bs=3; bs>=0; bs--) {
 
                        if(base[bs]) {
                            if(bs+val >= 4) {
                                result++;
                                base[bs] = false;
                            }
                            else {
                                base[bs+val] = true;
                                base[bs] = false;
                            }
                        }
                    }
                    base[0] = true;
                    index++;
                    index%=9;
                    j--;
                }
            }
        }
        // TODO Auto-generated method stub
        return result;
    }
}