[ps] n*n배열을 두개의 그룹으로 나눠서 연산을 구할때 시간최적화

14889번: 스타트와 링크

위의 문제로 예를 들어서,

n명의 선수가 있고, 0번팀과 1번팀으로 선수들을 나눠서, 0번팀의 능력치합과 1번팀의 능력치합을 계산해야 하는 상황이다.
이 때, permutation을 사용하기 위해서 team=[0,1,1,0,...,1]이라고 하고,

n*n의 반복문을 돌면서 i와 j가 같은 팀일 때 각 팀의 능력치에 더해준다고 하면
\(O(n^2)\)의 시간복잡도를 가지게 된다.

int calcgap(){
  int team0=0, team1=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(i==j) continue;
      // mask[i]에는 i의 팀 번호가 저장되어있다.
      if(mask[i]==0 && mask[j]==0) {team0+=stat[i][j]; continue;} 
      if(mask[i]==1 && mask[j]==1) {team1+=stat[i][j]; continue;}
    }
  }
  return abs(team0-team1);
}

---

이번에는 0번팀과 1번팀을 각각의 vector<int>에 담은다음 각 팀에서 반복문을 돌면서 능력치를 구한다면

\( O((\frac{n}{2})^{2}*2)=O(\frac{n^2}{2}) \) 의 시간복잡도를 가지게 된다.

그 이유는 수식에서 찾아볼 수 있다.

int calcgap(){
  vector<int> team0, team1;
  for(int i=0; i<n; i++){
    if(mask[i]==0) team0.push_back(i);
    else team1.push_back(i);
  }
  int gap=0;
  for(int i=0; i<n/2; i++){
    for(int j=i+1; j<n/2; j++){
      int a=team0[i], b=team0[j];
      gap+=stat[a][b];
      gap+=stat[b][a];
    }
  }
  for(int i=0; i<n/2; i++){
    for(int j=i+1; j<n/2; j++){
      int a=team1[i], b=team1[j];
      gap-=stat[a][b];
      gap-=stat[b][a];
    }
  }
  return abs(gap);
}

실제로 시간이 절반정도로 줄어든 것을 확인할 수 있다.