Educational Codeforces Round 115 (Rated for Div. 2)-B. Groups

문제 설명

$n$명의 학생들은 프로그래밍 수업의 첫 수업을 참여했다 ($n$은 짝수이다). 모든 학생들은 반드시 두 그룹으로 나뉘어야 한다. 각 그룹에 속한 학생은 반드시 주중에 있는 요일(월요일, 화요일, 수요일, 목요일, 금요일) 중 한 요일에 참가할 수 있어야 한다. 그리고 각 그룹이 선택한 요일은 반드시 서로 달라야 한다. 마지막으로 각 그룹에 속해있는 학생들의 숫자는 서로 같아야 한다.

각 학생들은 어느 요일에 수업을 참여할 수 있는지, 없는지를 적게하는 설문지를 채워서 제출했다.

우리가 해야할 것은 두 그룹의 시간 계획을 세우기 위해서 주중에 있는 서로 다른 요일을 선택할 수 있는지 없는지 결정하는 것이다. (첫번째 그룹은 첫번째 선택한 요일에 반드시 수업을 참여해야 하고, 두번째 그룹은 두번째 선택한 요일에 반드시 수업을 참여해야 한다.) 그리고 학생을 두 그룹으로 나누어야 하기 때문에 각 그룹은 같은 크기를 가져야한다. 각 그룹에서 정한 요일은 그룹에 속한 학생들이 모두 편하다고 응답한 요일이어야 한다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 학생의 수 $n (2 \le n \le 1000)$ 이 주어진다.

다음 $n$개의 줄에 걸쳐서 각 $i$번째 줄에는 $0$과 $1$로만 이루어진 $5$개의 정수가 주어진다. 만약 $i$번째 줄에 있는 $j$번째 수가 $1$이면 $i$번째 학생은 $j$번째 요일에 수업을 참여할 수 있다, 즉 편한 요일이라는 뜻이다. 만약 $j$번째 정수가 0이면 $i$번째 학생은 $j$번째 요일에 수업을 참여 할 수 없다는 뜻이다.

Output
각 테스트케이스 마다 모든 학생을 서로 다른 날을 선택할 수 있는 두 그룹으로 정확히 나눌 수 있으면 "YES" 그렇지 않으면 "NO"를 출력한다.

Example
input
2
4
1 0 0 1 0
0 1 0 0 1
0 0 0 1 0
0 1 0 1 0
2
0 0 0 1 0
0 0 0 1 0

output
YES
NO

문제 접근

사용한 알고리즘: 완전탐색, 수학, 구현
걸린 시간 : 00:05
생각을 해내는데 조금 오래 걸렸지만 결국 30분만에 해결한 문제라서 개인적으로 뿌듯했었다. 학교에서 공부를 할때 집합쪽에는 자신이 있어서 그런지 계속 생각해 봤고, 내가 생각한 접근법이 문제에서 제시한 모범답안과 같아서 너무 기분이 좋았다. 나도 점점 발전하는 것이 느껴진다. 조금만 더 노력해서 일단 그린부터 도전해보자.

일단 5개 요일에 2개의 팀이 들어갈 수 있는지 확인을 하는 것이기 때문에 우리는 $5 \times 5 = 25$ 번만 반복하면 모든 경우의 수를 찾을 수 있으므로 완전탐색으로 이 문제를 푸는 것이 맞다고 생각했다.

그렇다면 우리가 처음으로 1번팀을 월요일, 2번팀을 화요일에 배치한다고 생각해보자. 두 팀을 각각 집합으로 생각하고 가장 먼저 우리가 따져야할 조건은 무엇일까?

• 모든 사람을 완벽히 2팀으로 나눠야하기 때문에 월요일과 화요일에 수업을 들을 수 있는 사람들의 합집합이 전체집합이어야 한다. 즉 모든 사람들이 월요일과 화요일 둘중의 한 요일에 수업을 들을 수 있어야 한다는 뜻이다.
• 두 집합의 합집합이 전체집합인 상태에서, 한쪽만 수업을 들을 수 있는 사람이 절반보다 많으면 어떤일이 벌어질까? 그렇다면 두 팀을 완전히 절반으로 나눌 수 없게 된다. 여기서 한쪽만 수업을 들을 수 있는 사람은 교집합이 아니라 A - B집합, 즉 차집합인 개념이다.

따라서 우리는 모든 두 요일을 확인을 하는데, 그 요일마다 확인해야할 것은

1. 두 요일 모두 수업을 들을 수 있는 사람의 수
2. A요일만 수업을 들을 수 있는 사람의 수
3. B요일만 수업을 들을 수 있는 사람의 수

이고, 합집합은 1 + 2 + 3으로 절반보다 큰지 확인하는 구역은 2번과 3번 경우에만 한정해서 코드를 구현하면 된다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[n][5];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 5; j++) cin >> arr[i][j];
        }

        bool flag = false;
        for(int i = 0; i < 5; i++){
            for(int j = i + 1; j < 5; j++){
                int a = 0, b = 0, c = 0;
                for(int k = 0; k < n; k++){
                    a += (arr[k][i] && !arr[k][j]);
                    b += (!arr[k][i] && arr[k][j]);
                    c += (arr[k][i] && arr[k][j]);
                }
                flag |= (a + b + c == n && a <= n / 2 && b <= n / 2);
            }
        }
        cout << (flag ? "YES" : "NO") << "\n";
    }
    return 0;
}