[백준] 6987 월드컵

 

문제가 참 완탐스럽게 생겼다

처음에는 그리디로 쭉 보는건가 싶었는데

하다보니.. 그냥 편하게 백트래킹으로 풀었따

 

모든경우의 수 중에서 가지치기를 하면서 보면 시간안에 빠르게 들어온다

 

먼저 총 15가지의 라운드가 있고 각 라운드는 3가지의 경우의 수가 가능하다

그래서 3^15의 경우의 수가 있다

이 중에서 우리는 4개의 입력으로 받은 조건들을 만족하는 경우를 찾아야 한다

 

그래서 입력조건을 벗어나는 경우는 적절하게 가지치기를 해줘야한다

 

나의 경우는 order라는 배열에 일단 15라운드의 prev VS next를 다 저장했다

ex) [A,B],[A,C],[A,D]...[E,F] 

 

그 후 order배열에 0(prev 승),1(무),2(prev 패)를 넣어보면 된다

 

그러게 status라는 배열에 현재 라운드의 결과를 저장하고

만약 입력받은 결과를 만족시킬 수 있다면 다음 라운드로 넘어가고

아니라면 넘어가지 않는다

 

문제 자체는 쉬운데 구현하는게 좀 더러웠다...

 

소스코드

import java.util.Scanner;
 
public class Main {
    public static int[][][] arr = new int[4][6][3];
    public static int[][] status = new int[6][3];;
    public static int[] answer= new int[4];
    public static int[][] order = new int[15][2];
    public static int[] temp = new int[15];
    
    public static void answerCheck() {
        for(int i=0;i<4;i++) {
            boolean check=true;
            for(int j=0;j<6;j++) {
                for(int k=0;k<3;k++) {
                    if(arr[i][j][k] != status[j][k]) check=false;
                }
            }
            if(check) answer[i]=1;
        }
    }
    
    public static void solve(int pos) {
        if(pos==15) {
            answerCheck(); return;
        }
        int prev = order[pos][0];
        int next = order[pos][1];
        for(int i=0;i<3;i++) {
            status[prev][i]++;
            status[next][2-i]++;
            int cnt=0;
            for(int j=0;j<4;j++) {
                boolean can=true;
                for(int k=0;k<3;k++) {
                    if(status[prev][k]>arr[j][prev][k] || status[next][k]>arr[j][next][k]) can=false;
                }
                if(can) cnt++;
            }
            if(cnt!=0) solve(pos+1);
            status[prev][i]--;
            status[next][2-i]--;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i=0;i<12;i++) {
            if(i<5) order[i][1]=i+1;
            else if(i<9) {
                order[i][0]=1;
                order[i][1]=i-3;
            } else {
                order[i][0]=2;
                order[i][1]=i-6;
            }
        }
        order[12][0]=order[13][0]=3;
        order[12][1]=order[14][0]=4; 
        order[13][1]=order[14][1]=5;
        for(int i=0;i<4;i++) {
            for(int j=0;j<6;j++) {
                for(int k=0;k<3;k++) {
                    arr[i][j][k]=sc.nextInt();
                }
            }
        }
        solve(0);
        for(int i=0;i<4;i++) System.out.print(answer[i]+" ");
        
    }
}