BOJ 1304 : 지역

• 문제 링크 : boj.kr/1304
• 난이도 : G3
• 태그 : 그래프 이론, 완전탐색

1304번: 지역

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> arr(n+1);
    for(int i = 0; i < m; i++) {
        int s, e;
        cin >> s >> e;
        if(s < e) continue;
        for(int j = e; j < s; j++) {
            arr[j] = 1;
        }
    }

    for(int i = 1; i <= n; i++) {
        if(n % i) continue;
        bool flag = false;
        for(int j = i; j <= n; j += i) {
            if(arr[j]) {
                flag = true;
                break;
            }
        }
        if(flag) continue;
        cout << n / i;
        return 0;
    }

    return 0;
}

---

풀이

고속도로로 인해 $1 \le A < B \le N$인 도시 A에서 도시 B로 가는 경로는 항상 존재한다.

이는 하나의 지역에 속한 도시들은 연속되어야 함을 의미한다.

만약 연속되지 않는다면 하나의 지역은 다른 지역의 일부를 사이에 끼게 될 것이다.

$1 \le A < B < C \le N$이고 도시 A, C는 지역 1에, 도시 B는 지역 2에 속한다고 하자. 앞에서 관찰한 바에 의해 도시 A에서 도시 B로 가는 경로는 존재하며 동시에 도시 B에서 도시 C로 가는 경로가 존재한다. 이는 문제에서 설명한 조건에 반대되므로 하나의 지역에 속한 도시들은 연속되어야 함을 알 수 있다. 

 

이제 일반도로에 대해서 살펴보자.

만약 일반도로 i가 $S_i < E_i$라면 이 도로는 기존의 경로에 아무런 영향을 주지 않는다. 

중요한 일반도로는 $S_i$가 $E_i$보다 큰 도로이다. $E_i$에서 $S_i$로 가는 경로가 이미 존재하고, $S_i$에서 $E_i$로 가는 경로가 생겨 $S_i$와 $E_i$는 하나의 지역이 되어야 한다. 이때 앞에서 발견한 사실로 인해 $E_i$부터 $S_i$까지의 모든 연속된 도시는 하나의 지역이 되어야 한다.

 

어떤 도시들이 연결되어야 하는지 구했으므로 실제 지역을 구해보자.

모든 지역은 같은 수의 도시를 가져야 하므로, 한 지역에 K개의 도시가 들어간다고 가정해볼 수 있다.

한 지역 안의 모든 도시는 연결되어야 하므로, 각 지역은 1~K, K+1~2K, $\cdots$의 도시들로 이루어진다고 할 수 있다.

앞에서 연속되어 있어야 하는 도시들을 구했으므로 K, 2K, 3K, $\cdots$들이 다음 도시와 연결되어야 하는지를 확인하고 만약 모두가 그렇지 않다면 크기가 K인 지역들을 만들 수 있다.

 

결론적으로 N의 약수인 K를 1부터 확인하여 답을 구할 수 있다.