[swexpert] 6808. 규영이와 인영이의 카드게임 (java, D3)

한 명의 카드 순서는 고정이라 다른 한 사람의 모든 카드 배열 9! 만큼 순열로 돌리면서 구하면 된다.

비기는 경우는 고려하지 않고 이기거나 지는 경우만 구한다

dfs로 nPr(순열)을 구현하자

 

import java.util.Scanner;
 
public class Solution {
    static int t;
    static int card[];
    static int a[],b[];
    static int ans,ans2;
    static int sum,sum2;
    static int p[];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        t=sc.nextInt();
        for (int tc = 1; tc <=t; tc++) {
            card=new int[19];
            a=new int[9];
            b=new int[9];
            p=new int[9];
            for (int i = 0; i < 9; i++) {
                int num=sc.nextInt();
                card[num]=1;
                a[i]=num;
            }
             
            int idx=0;
            for (int i = 1; i <= 18; i++) {
            //나머지 카드 
                if(card[i]==0) {
                    b[idx++]=i;
                }
            }
            ans=0;
            ans2=0;
            nPr(0,0);
     
            System.out.printf("#%d %d %d\n",tc,ans,ans2);
        }
    }
    private static void nPr(int flag,int cnt) {
        if(cnt==9) {
            sum=0;
            sum2=0;
            for (int i = 0; i < 9; i++) {
                if(a[i]>p[i])sum+=a[i]+p[i];
                if(a[i]<p[i]) sum2+=a[i]+p[i];
            }
            if(sum>sum2)ans+=1;
            if(sum<sum2)ans2+=1;
            return;
        }
         
        for (int i = 0; i < 9; i++) {
            if((flag&1<<i)!=0)continue;
            p[cnt]=b[i];
            nPr(flag|1<<i,cnt+1);
        }
    }
}