백준 6987번 월드컵 (boj/6987.c)

비트마스킹을 사용합니다. 8진법 마스킹, 3진법 마스킹을 사용하는데요, 설명보다 코드를 보는 편이 더 이해가 빠르실겁니다. 시간복잡도는 정확하게는 잘 모르겠으나 얼마 안 나옵니다. 팀의 수 n=6에서 대략 350번? 쯤 for문을 돕니다.

#include <stdio.h>
#include <math.h>
typedef long long lint;
int co_game(int game){ return 2-game; }
int solve(lint mask, int num){
    lint lim, calc;
    lint new_mask;
    int game[3] = { 0, };
    int temp[3] = { 0, };
    int val, cnt, sft;
    int res=0;
    if(!num){ return mask?0:1; }
    game[2]=mask>>6&0x7; game[1]=mask>>3&0x7; game[0]=mask>>0&0x7;
    lim=(lint)(pow(3, num-1)+0.5);
    for(lint c=0;c<lim;c++){
        temp[0]=temp[1]=temp[2]=0;
        for(calc=c,cnt=0;cnt<num-1;calc/=3,cnt++){ temp[calc%3]++; }
        if(game[0]!=temp[0] || game[1]!=temp[1] || game[2]!=temp[2]){ continue; }
        new_mask=mask>>9;
        for(calc=c,cnt=0;cnt<num-1;calc/=3,cnt++){ 
            sft = 3*(3*cnt + co_game(calc%3));
            if((new_mask>>sft&0x07) == 0){ break; }
            new_mask -= (lint)1<<sft; }
        if(cnt!=num-1){ continue; }
        res |= solve(new_mask, num-1);
    }
    return res;
}
int main(void){
    lint mask;
    int inp;
    for(int c=0;c<4;c++){
        mask=0;
        for(int i=0;i<18;i++){
            scanf("%d", &inp);
            mask<<=3; mask|=inp; }
        printf("%d ", solve(mask, 6));
    }
    return 0;
}