[백준] No.14889 - 스타트와 링크 (C++, 비트마스크)

문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

풀이

 

solved.ac 난이도: Sliver 3

 

비트 마스크로 분류되어 풀어보았는데 사실상 메모리 제한이 크기 때문에 다른 기법으로도 충분히 해결 가능했던 문제이다.

본인은 비트마스크로 모든 경우의 수를 살펴보는 브루트포스 알고리즘을 사용했다.

 

비트 마스크로 사람의 수(player_num)를 반으로 나눈 팀을 형성하기 위해 아래와 같이 

1~(1<<player_num -1)까지의 모든 수에서 이진수로 나타낼 시 1이 나오는 개수를 구했다.

 

  int MAX_BIT =((1<<player_num)-1); for(int bits =1; bits<= MAX_BIT ; ++bits){
    temp_bits = bits;
    count =0;
    while(temp_bits >0){
      if(temp_bits & 1)
        ++count;
      temp_bits = temp_bits >>1;
    }
 
    if(count == player_num/2){
      reverse_bits = bits^MAX_BIT;
      
      if(cache[bits] == -1 && cache[reverse_bits] == -1)
        min_gap = min(min_gap, abs(CalcAbility(bits) - CalcAbility(reverse_bits)));
    }
  }

 

1의 개수가 player_num/2 라면 팀(bits)이 형성된 것이므로 상대팀(reverse_bits)을 

reverse_bits = bits^MAX_BIT 로 구해준다.

ex)  bits = 1001, reverse_bits = 1001 XOR 1111 = 0110

 

이제 해당 팀의 이진수 표현 값들을 CalcAbility 함수에 넘겨 팀의 능력치를 계산해주자.

추가적으로 bits < reverse_bits 인 경우, 1~(1<<player_num -1)까지 순회하다보면 reverse_bits일 때 다시 한번 bits와 reverse_bits를 계산하게 되므로 cache를 이용해서 같은 연산을 방지해준다.

 

CalcAbility(int bits)는 bits에서 해당 위치의 진수표현이 1인 값들의 능력치 합을 모두 순회하며 더해준다.

int CalcAbility(int bits){
  int result=0;
  int i_cnt=0, j_cnt=0;
  for(int i=1; i<=MAX_BIT ; i = i<<1){
    if(bits & i){
      j_cnt=0;
      for(int j=1; j<=MAX_BIT ; j = j <<1){
        if(bits & j)
          result += board[i_cnt][j_cnt];
        ++j_cnt;
      }
    }
    ++i_cnt;
  }
  cache[bits] = result;
  return result;
}

 

 

 

코드