[백준] 16986: 인싸들의 가위바위보 - JAVA

in Algorithm on 구현

https://www.acmicpc.net/problem/16986

풀이

구현문제.

승패가 주어지고, 각각 어떤 어떤 동작을 할지 알려준다.

승패 테이블을 이용해 승,패를 판단하는 문제.

지우가 다른 동작들을 내면서 K승을 쌓으면 성공이다.

지우가 낼 동작을 순열을 통해 작성하고 게임을 진행한다.

지우가 K승 이상 쌓으면 true,

지우가 N번 이상 동작을 하면 같은 동작을 다시 내는 것이므로 false,

경희나 민호가 K승 이상 쌓으면 false이다.

메모리: 37796KB

시간: 248ms

언어: Java 11

코드

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

public class Main {
    static int N, K;
    static int[][] table;
    static int[] kyunghee, minho, jiwoo, win, idx;
    static boolean[] visit;
    static boolean flag;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        table = new int[N + 1][N + 1];
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < N + 1; j++) {
                table[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        kyunghee = new int[20];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 20; i++) {
            kyunghee[i] = Integer.parseInt(st.nextToken());
        }

        minho = new int[20];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 20; i++) {
            minho[i] = Integer.parseInt(st.nextToken());
        }

        flag = false;
        jiwoo = new int[N + 1];
        visit = new boolean[N + 1];
        makeJiwoo(0);

        System.out.println(flag ? 1 : 0);

    }

    private static void makeJiwoo(int cnt) {
        if (flag) {
            return;
        }
        if (cnt == N) {
            win = new int[3];
            idx = new int[3];
            game(0, 1);
            return;
        }
        for (int i = 1; i < N + 1; i++) {
            if (visit[i]) {
                continue;
            }
            visit[i] = true;
            jiwoo[cnt] = i;
            makeJiwoo(cnt + 1);
            visit[i] = false;
        }
    }

    private static void game(int a, int b) {
        if (win[0] >= K) {
            flag = true;
            return;
        }

        if (idx[0] >= N || win[1] >= K || win[2] >= K) {
            return;
        }

        int nextPlayer = 0;
        for (int i = 0; i < 3; i++) {
            if (a != i && b != i) {
                nextPlayer = i;
                break;
            }
        }
        int p1 = 0;
        switch (a) {
            case 0:
                p1 = jiwoo[idx[0]++];
                break;
            case 1:
                p1 = kyunghee[idx[1]++];
                break;
            case 2:
                p1 = minho[idx[2]++];
        }

        int p2 = 0;
        switch (b) {
            case 0:
                p2 = jiwoo[idx[0]++];
                break;
            case 1:
                p2 = kyunghee[idx[1]++];
                break;
            case 2:
                p2 = minho[idx[2]++];
        }

        int result = table[p1][p2];

        if (result == 2) {
            win[a]++;
            game(a, nextPlayer);
        } else if (result == 0) {
            win[b]++;
            game(nextPlayer, b);
        } else {
            if (a > b) {
                win[a]++;
                game(a, nextPlayer);
            } else {
                win[b]++;
                game(nextPlayer, b);
            }
        }

    }
}