[SWEA/C++] 서로소 그리드 (No. 20731)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 GCD를 이용하면 쉽게 풀 수 있는 문제다.

 

문제를 보면 GCD(k+i, k+j)가 1이면 1, 아니면 ?를 N*N 배열에 기록한다.

이때, 이 배열의 조건에 만족하는 k가 존재하는지 판단하는 문제다.

 

이 문제에서 중요한 점은 K의 범위가 정해져 있지 않기 때문에 모든 조건에 맞는 K가 있는지 확인하면 된다.

 

그렇다고 모든 K에 대해 탐색할 수는 없다.

그러면 GCD(k+i, k+j)를 어떻게 표현할 수 있을까?

 

i > j의 조건을 만족하는 경우에 GCD(k+i, k+j)가 1이 아니라면 GCD(k+i, i-j)도 1이 아니다.

 

왜 그런지 잘 생각해보면 GCD(k+i, k+j)가 임의의 GCD 값인 g를 갖는다고 가정하자.

 

k+i와 k+j를 아래와 같이 표현할 수 있다.

$$ k+i = k+j+g*n $$

왜냐하면 k+i와 k+j가 g의 배수이기 때문에 i > j를 만족하므로 g * n (n은 1이상의 정수)를 만족하는 n이 존재한다.

 

이제 이를 이용하면 i - j = g * n이 된다.

그러므로 GCD(k+i, k+j) = GCD(k+i, i-j)로 표현할 수 있다.

 

이제 다음으로 고려해야할 점은 범위다.

 

그림을 보며 이해해 보자.

 

예를 들어 i - j 가 3일 경우 GCD(k+i, 3)의 값이 1이 아닌 경우는 3 칸 간격으로 나타난다.

 

여기서 말하는 1이 아닌 경우가 3칸 간격으로 나타난다는게 무슨 의미인지 설명하면

1. GCD(k+i, 3)

2. GCD(k+i+1, 3)

3. GCD(K+i+2, 3)

 

위 3가지 GCD 중에 적어도 하나는 GCD가 3이라는 뜻이다.

 

잘 생각해보면 연속된 3개의 정수를 선택하면 그 중 하나는 3의 배수임은 자명한 사실이다.

(왜냐하면 3의 배수라는 뜻은 임의의 수 k를 3으로 나누었을 때 나머지가 0인 경우인데 나머지가 0, 1, 2, 순서로 반복하며 나타나기 때문에 연속된 3개의 정수를 고르면 3의 배수가 포함될 수 밖에 없다.

 

이제 위 규칙을 알았으므로 다음으로 고려해야할 규칙을 알아보자.

 

사실 위 규칙은 i-j가 소수일 때만 고려하면 된다.

 

왜냐하면 i - j가 소수가 아닌 임의의 정수 a를 생각해보자. 그러면 a의 약수인 b가 존재한다.

 

이때, GCD(k+i, a)가 1인지 확인하기 위해서는 a의 모든 약수 b에 대해 GCD(k+i, b)가 1이여야 한다.

이 중 하나라도 GCD(k+i, b)가 1이 아니라면 GCD(k+i, a)는 1이 아닌 GCD(k+i, a)가 존재하게 되기 때문이다.

 

이를 이용하면 i-j가 소수인 경우, 소수가 아닌 경우에 대해 조건에 맞는 정수가 존재하는지 검사할 수 있다.

 

+ 추가로 고려해야하는 예외가 하나 더 있다.

바로 k가 0인 경우다.

k가 0인 경우는 특수한 경우로 i = 1, j = 1인 경우에 GCD(0+1, 0+1) = 1 이 된다.

이외에 모든 경우는 GCD(k+1,k+1) = ? 가 된다.

그러므로 GCD(k+1, k+1) = 1인 경우는 k가 0인 경우만 존재하므로 이에 대한 GCD를 전부 계산해 격자판이 정상적인 격자판인지 확인하면 된다.

 

 

​

[아이디어 정리]

1. GCD를 이용해 GCD(k+i, k+j)를 GCD(k+i, i - j)로 단순화 해 생각한다.
2. 만약 i - j가 소수라면, i - j칸마다 GCD(k+i, i - j) = ?인 경우가 나타난다.
3. 만약 i - j가 소수가 아니라면, 약수가 존재하므로 i - j의 모든 약수 b에 대해 GCD(k+i, b)를 검사하고 모든 약수에 대해 GCD가 1이라면 GCD(k+i, i - j) = 1이다.
4. 만약 하나의 약수라도 GCD(k+i, b) = ? 라면 GCD(k+i, i - j) 도 ? 값을 갖는다.
5. 만약 GCD(k+1, k+1) 위치의 값이 1이라면 k=0인 경우이므로 격자판이 정상적인지 GCD를 직접 계산한다.

 

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
 
vector<vector<int>> Primes;
 
int GCD(int a, int b) {
    if (b > a) {
        return GCD(b, a);
    }
    if (a % b == 0) {
        return b;
    }
    else {
        return GCD(b, a % b);
    }
}
 
bool CanMake() {
    int N;
    cin >> N;
    vector<vector<char>>graph(N + 1, vector<char>(N + 1));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> graph[i][j];
        }
    }
 
    if (graph[1][1] == '1') 
    {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int gcd = GCD(i, j);
                if (gcd == 1&& graph[i][j] != '1') {
                    return false;
                }
                if (gcd != 1&&graph[i][j]=='1') {
                    return false;
                }
            }
        }
    }
    else {
        for (int i = 1; i <= N; i++) {
            if (graph[i][i] != '?') {
                return false;
            }
        }
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                if (graph[i][j] != graph[j][i]) {
                    return false;
                }
            }
        }
        for (int i = 1; i < N; i++) {
            if (graph[i][i + 1] != '1') {
                return false;
            }
        }
        for (int a = 2; a < N; a++) {
            if (Primes[a].size() == 0) {
                // i-j = a가 소수 라면
                int idx = 0;
                bool flag = true;
                for (int i = 1; i <= N; i++) 
                {
                    if (i + a > N) {
                        break;
                    }
 
                    if (graph[i][i + a] == '1') {
                        idx ++;
                        if (idx >= a) {
                            return false;
                        }
                    }
                    else { //? 라면
                        if (idx != a - 1)
                        {
                            if (!flag)
                            {
                                return false;
                            }
                        }
                        idx = 0;
                        flag = false;
                    }
                }
            }
            else {
            // i - j = a 가 소수가 아니라면
                for (int i = 1; i <= N; i++) {
                    if (i + a <= N) {
                        bool flag = true;
                        if (graph[i][i + a] == '?') {
                            for (int j = 0; j < Primes[a].size(); j++) {
                                if (graph[i][i + Primes[a][j]] == '?')
                                {
                                    flag = true;
                                    break;
                                }
                                else {
                                    flag = false;
                                }
                            }
                        }
                        else {
                            for (int j = 0; j < Primes[a].size(); j++)
                            {
                                if (graph[i][i + Primes[a][j]] == '?')
                                {
                                    flag = false;
                                    break;
                                }
                            }
                        }
                        if (!flag) {
                            return false;
                        }
                    }
                }
            }
        }
 
        return true;
    }
 
}
 
int main() {
    Primes = vector<vector<int>>(51);
    for (int i = 4; i < Primes.size(); i++) {
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                Primes[i].push_back(j);
            }
        }
    }
    
    int tc;
    cin >> tc;
     
    for (int t = 1; t <= tc; t++)
    {
         
        if (CanMake()) {
            cout << "#" << t << " YES\n";
        }
        else {
            cout << "#" << t << " NO\n";
        }
    }
 
    return 0;
}

 

---

GCD에 대해서 왜 이렇게 생각할 수 있는지 정리하다보니 오래 걸린 문제였다.

단순한 비교 대신 GCD에 대해 이해하고 있다면, 방법을 생각할 수 있는 문제다.

 

SW Expert Academy