You will be fine

<Algorithm> 142. 인싸들의 가위바위보(BJO)

by BFine
반응형

1. 16986번 인싸들의 가위바위보(BJO)

  • 시뮬레이션, 완전탐색문제

  • 이 문제는 살짝 설명이 부족하여 이유를 찾느라 오래 걸렸다. 

  • 지우가 모든 경우를 다내지 않아도 이기면 끝, 명희&민호도 각라운드로 내는것이 아닌 자기차례에 안쓴 것을 낸다.

  • 위의 두가지 때문에 테케에서 자꾸 틀리는 일이 발생했다 ...

  • 이런 유형의 문제는 어렵진 않지만 문제이해, 규칙 찾는것이 중요하고 시간도 중요하다.

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int n;
    static int k;
    static int[][] map;
    static int[] kyung = new int[20];
    static int[] minho = new int[20];
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); //손동작수
        k = sc.nextInt(); // 승수
        map = new int[n][n];
        /******************************
         * 지우가 낼 수 있는 모든 경우의 수를
         * 완전탐색하여 지우가 먼저 우승 하면 1
         * 을 아니면 0을 출력한다.
         *******************************/
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        
        for(int i = 0; i < 20; i++) {
            kyung[i] = sc.nextInt()-1;
        }
        for(int i = 0; i < 20; i++) {
            minho[i] = sc.nextInt()-1;
        }
        visited = new boolean[n];
        permu(""0);
        System.out.println(ans);
    }
    static int ans = 0;
    static boolean[] visited;
    public static void permu(String order,int deep) {
        if(deep == n) {
            ans = Math.max(ans, solve(order));
            return;
        }
        
        for(int i = 0; i < n; i ++) {
            if(!visited[i] && ans == 0) {
                visited[i] = true;
                permu(order+i,deep+1);
                visited[i] = false;
            }
        }
    }
    public static int solve(String order) {
        
        char[] jiwu = order.toCharArray();
        final int jiwu_order = 0;
        final int kyung_order = 1;
        final int minho_order = 2;
        int[] winner = {0,0,0};
        int cnt = 0;
        int cnt_kyung = 0;
        int cnt_minho = 0;
        int round = 0;
        Queue<Integer> order_match = new LinkedList<>();
        order_match.add(jiwu_order);
        order_match.add(kyung_order);
        order_match.add(minho_order);
        
        while (round < 20) {
            int pre = order_match.poll();
            int post = order_match.poll();
            int wait = order_match.poll();
            
            int res = 0;
            
            if(jiwu_order== pre && kyung_order == post) {
                res = map[jiwu[cnt++]-'0'][kyung[cnt_kyung++]];
            }else if(jiwu_order == pre && minho_order == post) {
                res = map[jiwu[cnt++]-'0'][minho[cnt_minho++]];
            }else if(kyung_order == pre && jiwu_order == post){
                res = map[kyung[cnt_kyung++]][jiwu[cnt++]-'0'];
            }else if(kyung_order == pre && minho_order == post) {
                res = map[kyung[cnt_kyung++]][minho[cnt_minho++]];
            }else if(minho_order == pre && jiwu_order == post) {
                res = map[minho[cnt_minho++]][jiwu[cnt++]-'0'];
            }else if(minho_order == pre && kyung_order == post) {
                res = map[minho[cnt_minho++]][kyung[cnt_kyung++]];
            }
            
            if(res == 1) {
                if(pre < post) res = 0;
                else res = 2;
            }
            
            if(res == 2) {
                winner[pre]++;
                order_match.add(pre);
                order_match.add(wait);
                order_match.add(post);
            }else if(res == 0) {
                winner[post]++;
                order_match.add(post);
                order_match.add(wait);
                order_match.add(pre);
            }
            
        
            if(winner[0== k || winner[1== k || winner[2== k) {
                if(winner[0== k ) {
                    return 1;
                }
                else return 0;
            }
            
            if(!(cnt < n)) return 0;
            round++;
        }
        return 0;
    }
}
 
cs


참고 & 출처  

블로그의 프로필 사진

블로그의 정보

57개월 BackEnd

BFine

활동하기