Educational Codeforces Round 113 (Rated for Div. 2)-B. Chess Tournament

문제 설명

$n$명의 체스 선수가 참여할 체스 토너먼트가 곧 시작합니다! 모든 참가자는 다른 모든 참가자와 한번씩 게임을 진행해야 합니다. 한 경기가 끝나면 한 사람이 이기고, 다른 사람이 지는 경우와 두 참가자 모두 비기는 경우가 생깁니다.

각 참가자는 자신만의 성향을 가지고 있는데, 그 성향은 다음 중 하나입니다.

1. 자신이 참여한 모든 게임에 지기 싫어하는 사람(즉 한번이라도 지지 않고 토너먼트를 종료해야함.)
2. 최소 1번의 경기에 승리하고 싶어하는 사람

우리가 할 일은 모든 참가자의 성향을 만족하는 토너먼트 결과표가 존재하는지 아닌지 결정을 하는 것입니다. 만약 다양한 결과표가 존재하면 그것중 하나를 출력한다. 만약 존재하지 않는다면 불가능하다고 말해야 합니다.

Input
첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 200)$

각 테스트케이스의 첫번째 줄에는 체스 참가자 수 $n$이 주어진다. $(2 \le n \le 50)$

각 테스트케이스의 두번째 줄에는 $n$자리로 이루어진 문자열 $s(|s| = n, s_i \in {1, 2})$가 주어진다. 만약 $s_i = 1$ 이면 $i$번째 참가자는 1번 성향을 가지고 있고, 그렇지 않으면 2번 성향을 가지고 있다.

Output
각 테스트 케이스마다 다음 양식에 따라 출력한다.
첫번째 줄에는 모든 참가자의 성향을 충족하지 못하면 "NO"를 출력한다.
그렇지 않으면 "YES"를 출력한다. 그리고 다음 $n$번째 줄에는 $n \times n$크기의 행렬을 출력한다.
행렬의 $i$번째 행과 $j$번째 열에 속한 원소는 다음에 설명할 경우 중 하나를 만족해야한다.

• 만약 $i$번째 참가자가 승리하고, $j$번째 참가자가 패배하면 => +
• 만약 $i$번째 참가자가 패배하고, $j$번째 참가자가 승리하면 => -
• 만약 $i$번째 참가자와 $j$번째 참가자가 비겼으면 => =
• 만약 $i = j$이면 => X

Example
input
3
3
111
2
21
4
2122

output
YES
X==
=X=
==X
NO
YES
X--+
+X++
+-X-
--+X

문제 접근

사용한 알고리즘: 구현, 구성적
걸린 시간 : 00:21
virtual contest에서 1시간 정도 걸려서 겨우겨우 푼 문제이다. 문제접근방식은 contest를 끝나고 editorial을 보니까 맞았는데, 이 접근 방식을 생각하기 위해서 1시간 가량 생각을 했다. 그래도 희망적인 소식은 보통 문제를 봐도 풀지 못한다 -> 문제를 오랫동안 생각해서 결국 풀어낸다. -> 문제를 보고 바로 풀이가 생각난다. -> 문제를 바로바로 푼다. 순으로 실력이 향상된다고 생각하는데, 내가 지금 2단계에 있으니까 조금만 더 연습하면 codeforce B번 문제는 잘 풀 수 있을 거라고 자신감을 가지면서 이 문제의 풀이를 시작하려고 한다.

먼저 주어진 참가자의 유형을 보고 모든 참가자의 성향을 맞출 수 있는 경기표를 만들 수 있는지 없는지 부터 판별을 해야한다. 1번 성향을 가진 참가자를 유심히 보자. "이 유형의 참가자는 패배만 안하면 되기 때문에 무승부만 하면 되지 않을까?"라는 생각을 먼저 하면 이 문제의 접근이 시작된다. 1번 유형끼리 승패가 나뉘어지는 순간 한번이라도 패배를 하면 안된다는 1번 성향을 가진 참가자의 충족을 만족시켜줄수 없기 때문이다.

4명의 참가자가 있다고 가정해보자.
모든 참가자가 1번 유형이라고 가정하면 위에서 생각한 방식대로 모두 서로 무승부를 하면 1번 유형의 니즈를 충족시킬 수 있다.
그렇다면 참가자중 1명만 1번 유형이고 나머지는 2번 유형이라고 가정해보자. 일단 1번 유형의 참가자랑 맞붙으면 모두 무승부를 한다. 2번 유형은 최소 1번은 승리를 해야하는데, 사람이 3명이기 때문에 각자 1번씩 승리를 하면 2번 유형의 참가자의 니즈또한 충족시킬 수 있다. 그리고 이 부분부터가 문제를 푸는데 굉장히 중요하다.
3명이 2번 유형일때 성적표를 보자.
X+-
-X+
+-X
1번이 2번을 이기고, 2번이 3번을 이기고, 3번이 1번을 이기는 성적표를 만들면 가볍게 만들 수 있다.
2명이 2번 유형일때 성적표를 보자.
X+
-X
어라? 2명이 2번 유형이면 한사람이 이기면 반드시 다른 사람은 져야하는데, 경기는 한번 뿐이니 모든 사람의 성향을 충족시킬 수 없다!!
1명이 2번유형이고 나머지가 1번 유형이면 1번 유형끼리는 반드시 무승부가 되야하는데, 2번 유형은 한번을 이기고 싶어한다. 이 상황 자체가 모순이다.

이제 문제의 실마리가 보이기 시작할 것이다.

어떠한 경우라도 2번 유형의 참가자가 2명 혹은 1명이면 2번 유형의 참가자의 성향을 충족 시킬수 없다. 이 주장은 위에서 말한 예시로 증명할 수 있다.
그렇다면 이제 안되는 경우를 찾았으니, 되는 경우를 어떻게 구성하면 좋을지 생각해 봐야하는데, 이것 또한 위에서 설명한 예시를 통해서 답이 나온다. 1번 유형끼리는 모두 무승부를, 2번 유형끼리 사람들은 순환하면서 승패를 반복하면 (1번이 2번을 이기고, 2번이 3번을 이기고, 3번이 1번을 이기는 방식) 모든 참가자의 욕구를 충족시킬 수 있는 성적표가 나온다.

정답 코드

#include <iostream>
#include <vector>
#include <string>
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;
        char cnt[n];
        vector<int> v;
        for(int i = 0; i < n; i++){
            cin >> cnt[i];
            if(cnt[i] == '2') v.push_back(i);
        }

        if(v.size() == 1 || v.size() == 2) cout << "NO" << "\n";
        else{
            cout << "YES" << "\n";
            vector<string> arr(n, string(n, '='));
            for(int i = 0; i < n; i++) arr[i][i] = 'X';

            for(int i = 0; i < v.size(); i++){
                int cur = v[i], next = v[(i + 1) % v.size()];
                arr[cur][next] = '+';
                arr[next][cur] = '-';
            }

            for(int i = 0; i < n; i++) cout << arr[i] << "\n";
        }
    }
    return 0;
}