월드컵 (feat. 백준, 6987번)

월드컵
https://www.acmicpc.net/problem/6987

6987번: 월드컵

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
struct MatchCase{
    short first_team;
    short second_team;
};
short arr[6][3], goal[6][3];        // 3 => 0 : 승, 1 : 무, 2 : 패
MatchCase match_team_num[15];       // 매칭 가능한 경기는 총 15개
bool check;
void func(register short n){
    if(n == 15){
        for(register short i = 0, j; i < 6; ++i)
            for(j = 0; j < 3; ++j)
                if(arr[i][j] != goal[i][j])    // 15번 경기 중 arr와 goal이 다르면 더 이상 볼 필요 없으므로 다음 경기 확인
                    return;
        check = true;   // 위에서 15번 경기 중 모든 arr와 goal이 같으므로 이는 가능한 경기라는 의미.
        return;
    }
    register short team1_num = match_team_num[n].first_team, team2_num = match_team_num[n].second_team;
    // team1 승, team2 패
    ++arr[team1_num][0], ++arr[team2_num][2];
    func(n + 1);
    --arr[team1_num][0], --arr[team2_num][2];
    // team1 무, team2 무
    ++arr[team1_num][1], ++arr[team2_num][1];
    func(n + 1);
    --arr[team1_num][1], --arr[team2_num][1];
    // team1 패, team2 승
    ++arr[team1_num][2], ++arr[team2_num][0];
    func(n + 1);
    --arr[team1_num][2], --arr[team2_num][0];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    // 0팀과 경기 : 1, 2, 3, 4, 5
    // 1팀과 경기 : 2, 3, 4, 5
    // 2팀과 경기 : 3, 4, 5
    // 3팀과 경기 : 4, 5
    // 4팀과 경기 : 5
    // 즉, 가능한 A팀과 B팀의 총 경기 => match_team_num (15개)
    for(register short i = 0, j, t = 0; i < 6; ++i)
        for(j = i + 1; j < 6; ++j)
            match_team_num[t].first_team = i, match_team_num[t].second_team = j, ++t;
    for(register short t = 0; t < 4; ++t){
        for(register short i = 0, j; i < 6; ++i)
            for(j = 0; j < 3; ++j)
                cin >> goal[i][j], arr[i][j] = 0;
        check = false;
        func(0);
        cout << (check ? 1 : 0) << " ";
    }
    return 0;
}
// *&)*@*

 

반응형

완전탐색을 통해 접근하는 문제입니다.

경기가 가능한 모든 경우의 수에 대해서 승/무/패 를 임의대로 기록하고, 그 기록된 값이 문제로 주어진 경우와 같다면 가능 결과, 한번도 같지 않다면 불가능한 결과 라고 판단할 수 있습니다.

자세한 내용은 주석을 참고하시기 바랍니다.