티스토리 뷰

알고리즘/Java

[백준] 6987 월드컵

세진짱 2020. 5. 7. 02:51

 

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

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

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

 

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

 

먼저 총 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라는 배열에 현재 라운드의 결과를 저장하고

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

아니라면 넘어가지 않는다

 

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

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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]+" ");
        
    }
}
 
 
 

'알고리즘 > Java' 카테고리의 다른 글

[SWEA] 4050 재관이의 대량 할인  (0) 2020.04.29
[백준] 16234 인구이동  (0) 2020.04.24
[SWEA] 9659 다항식 계산  (0) 2020.04.03
[SWEA] 1244 최대상금  (0) 2020.02.17
[JUNGOL] 1828 냉장고  (0) 2020.02.12
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함