[BOJ] 백준 6987 월드컵

출처: https://www.acmicpc.net/problem/6987

 Input 

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4

4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3

5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5

5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

 

 Output 

1 1 0 0

단순히 이긴 횟수, 비긴 횟수, 패배한 횟수만을 비교해서 답을 구할 수 없습니다.

C 팀이 다른 누군가와 비겼다는 것은 상대방 전적에도 비긴 횟수가 있어야 하기 때문입니다.

승/패 역시 마찬가지로 누군가가 이겼다면 다른 상대방은 졌다는 것을 의미합니다.

 

① 6개팀이 승부하는 경우의 수는 15가지입니다.

A: {B, C, D, E, F}

B: {C, D, E, F}

C: {D, E, F}

D: {E, F}

E: {F}

 

② team 1 vs team 2의 결과는 3가지 입니다.

- 승리 / 패배

- 무승부

- 패배 / 승리

▶O(315)으로 각각의 수를 모두 구해서 입력받은 Case가 가능한지 확인합니다.

---

#include <iostream>
using namespace std;
 
const int team1[] = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 };
const int team2[] = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };
int answer[4], match[6][3], result[6][3];
 
void DFS(int tc, int round){
    // 15개 경기 종료
    if(round == 15){
        // 이미 가능한 경우로 판단된 경우
        if(answer[tc]) return;
 
        for (int r = 0; r < 6; r++) {
            for (int c = 0; c < 3; c++){
                // 예측 한 곳이라도 맞지 않는 경우
                if(match[r][c] != result[r][c])
                    return;
            }
        }
                
        // 모든 예측이 일치한다면 가능한 결과로 처리
        answer[tc] = 1;
        return;
    }
            
    // {승리(0), 무승부(1), 패배(2)}
    int t1 = team1[round];
    int t2 = team2[round];
 
    // t1 승, t2 패
    result[t1][0]++; result[t2][2]++;
    DFS(tc, round + 1);
    result[t1][0]--; result[t2][2]--;
 
    // t1 무, t2 무
    result[t1][1]++; result[t2][1]++;
    DFS(tc, round + 1);
    result[t1][1]--; result[t2][1]--;
 
    // t1 패, t2 승
    result[t1][2]++; result[t2][0]++;
    DFS(tc, round + 1);
    result[t1][2]--; result[t2][0]--;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for(int TC=0; TC<4; ++TC){
        for(int r=0; r<6; ++r){
            for(int c=0; c<3; c++){
                cin >> match[r][c];
            }
        }
        DFS(TC, 0);
    }
 
    for(int i=0; i<4; i++)
        cout << answer[i] << ' ';
    cout << "\n";
}