BOJ 1304 - 지역

image.png

연속적으로 그룹이 묶여야 한다는 것을 알면 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;  
    }  
  }  
}

Tags:

Categories:

Updated:

Comments