BOJ 6987번: 월드컵

문제

문제 바로가기> BOJ 6987번: 월드컵

6987번: 월드컵

 

풀이

경기가 진행될 수 있는 모든 경우의 수를 탐색하여,

그 중 하나라도 결과 값과 일치하는 게 있다면 (= 가능한 결과), 1을 출력하도록 풀었다.

 

모든 경우의 수를 탐색할 경우,

시간 복잡도는 3^15(=14,348,907)(*4 = 57,395,628)로
시간 내 완전탐색이 가능하다!

 

총 경기 경우의 수는 6C2 = 15 이고, (이 조합을 미리 만들어주는 부분이 make_team() 함수)

두 팀이 경기를 진행했을 때, 발생할 수 있는 경우는 총 3가지 이다.

 

    1. team1 승리

    2. 무승부

    3. team2 승리

 

C++

#include<iostream>
#include<vector>
#define TC 4
#define COUNTRY 6
#define MATCHCNT 15
using namespace std;

int ans;
int match[COUNTRY][3]; // 경기 결과 (승 무 패)
int game[COUNTRY][3];
vector<pair<int, int> > team;

void make_team(){
    for(int team1=0; team1<COUNTRY; team1++){
        for(int team2=team1+1; team2<COUNTRY; team2++) team.push_back({team1, team2});
    }
}

void input(){
    for(int i=0; i<COUNTRY; i++){
        for(int j=0; j<3; j++) cin >> match[i][j];
    }
}

bool check(){
    for(int i=0; i<COUNTRY; i++){
        for(int j=0; j<3; j++){
            if(match[i][j]!=game[i][j]) return false;
        }
    } return true;
}

void solution(int cnt){ // 6C2 = 15
    if(ans) return;  // 이미 가능한 결과, 더 볼 필요 없음
    if(cnt == MATCHCNT){
        if(check()) ans = 1; // 하나라도 일치하는 경우
        return;
    }

    int t1 = team[cnt].first;
    int t2 = team[cnt].second;

    // 승 패
    game[t1][0]++; game[t2][2]++;
    solution(cnt+1);
    game[t1][0]--; game[t2][2]--;

    // 무승부
    game[t1][1]++; game[t2][1]++;
    solution(cnt+1);
    game[t1][1]--; game[t2][1]--;

    // 패 승
    game[t1][2]++; game[t2][0]++;
    solution(cnt+1);
    game[t1][2]--; game[t2][0]--;

}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    make_team();

    for(int t=0; t<TC; t++){
        input();
        ans = 0;
        solution(0);
        cout << ans << " ";
    }
}

 

Java

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

public class Main {
	
	static final int TC = 4;
	static final int COUNTRY = 6;
	static final int  MATCHCNT = 15;
	
	static StringBuilder sb = new StringBuilder();
	static List<int[]> team = new ArrayList<>();
	static BufferedReader br = null;
	
	static int[][] match = new int[COUNTRY][3], game = new int[COUNTRY][3];
	static int ans = 0;

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		br = new BufferedReader(new InputStreamReader(System.in));
		
		make_team();
		
		for(int t=0; t<TC; t++) {
			input();
			ans = 0;
			solution(0);
			sb.append(ans + " ");
		}
		System.out.println(sb.toString());
	}

	private static void make_team() {
		for(int team1=0; team1<COUNTRY; team1++) {
			for(int team2=team1+1; team2<COUNTRY; team2++) {
				team.add(new int[] {team1, team2});
			}
		}
	}

	private static void input() throws Exception {
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<COUNTRY; i++) {
			for(int j=0; j<3; j++) {
				match[i][j] = Integer.parseInt(st.nextToken());
			}
		}
	}
	
	private static boolean check() {
		for(int i=0; i<COUNTRY; i++) {
			for(int j=0; j<3; j++) {
				if(match[i][j] != game[i][j]) return false;
			}
		} return true;
	}

	private static void solution(int cnt) {
		if(ans==1) return; // 이미 가능한 결과, 더 볼 필요 없음
		if(cnt == MATCHCNT) {
			if(check()) ans = 1;
			return;
		}
		
		int t1 = team.get(cnt)[0];
		int t2 = team.get(cnt)[1];
		
		// 승 패
		game[t1][0]++; game[t2][2]++;
		if(ans==0) solution(cnt+1);
		game[t1][0]--; game[t2][2]--;
		
		// 무승부
		game[t1][1]++; game[t2][1]++;
		if(ans==0) solution(cnt+1);
		game[t1][1]--; game[t2][1]--;
		
		
		// 패 승 
		game[t1][2]++; game[t2][0]++;
		if(ans==0) solution(cnt+1);
		game[t1][2]--; game[t2][0]--;
	}
}