BOJ 1304 - 지역
연속적으로 그룹이 묶여야 한다는 것을 알면 i -> i + 1로의 간선이 항상 있으므로 반대 방향으로 간선들을 봤을 때 현재 그룹 사이즈를 못만들게 하는 간선이 있는지를 확인하면 됩니다. 구간합 배열로 처리할 수도 있습니다.
void solve () {
int n, m;
cin >> n >> m;
vi psum(n);
vector<pi> edges;
for(int i =0;i<m;i++) {
int u, v; cin >> u >> v, u--, v--;
if(v > u) continue;
psum[v]++;
psum[u]--;
edges.pb({v, u});
}
for(int i = 1; i < n ; i++) psum[i] += psum[i-1];
for(int g = n; g >= 1; g--) {
if(n % g) continue;
int f = 1;
int group_size = n / g;
for(int i = group_size - 1; i < n; i += group_size) {
int l = i - g + 1, r = i;
if(psum[i]) f = 0;
}
if(f) {
cout << g;
return;
}
}
}
Comments