파일 한개에 대해서 스코어를 계산하는 방법이 있다. 선후공에 관계 없이 스코어가 양수이면 Alice가, 음수이면 Bob이 이기게 된다.
파일이 여러개가 있을때의 스코어는 각 파일의 스코어의 합이 된다. 이것이 양수이면 Alice가, 음수이면 Bob이 선후공에 관계 없이 이기게 되고, 이 값이 0이어야만 승자가 선후공여부에 따라서 달라지는 페어한 게임이 된다
파일의 스코어를 계산하는 방법은 우선 B만 한개 있는 파일의 스코어를 1로, W만 한개 있는 파일의 스코어를 -1로 정의한다. BB, W, W 이렇게 세개의 파일이 있을때 게임이 페어하게 되므로, score(BB) + 2*score(W) = 0 으로 쓸수 있고 BB의 스코어는 2가 된다. 마찬가지로 B, WB, WB 이렇게 세개의 파일이 있으면 게임이 페어하므로 WB의 스코어는 -1/2이 된다. 이런식으로 어떤 파일의 스코어를 기존에 스코어를 알고있는 파일들을 이용해서 페어게임을 만든 다음에 계산할수 있다. 이 스코어들은 항상 n/(2^k) 형태로 표현되는 값이 된다.
유튜브에서는 어떤 파일의 스코어를 구하는 공식을 알려주지는 않지만, 이제 대충 유도 가능하다.
맨 아래에서부터 같은 색이 연속되어 나오는 갯수만큼 1을 더하거나 (색이 B이면), 뺀다 (색이 W이면)
다른색이 처음 나오면 1/2을 더하거나 빼고, 그 이후부터는 계속 1/4, 1/8, 1/16, … 을 더하거나 뺀다.
예제
score(BBB) = 3
score(BBWB) = 2 - 1/2 + 1/4 = 7/4
score(BWBW) = 1 - 1/2 + 1/4 - 1/8 = 5/8
그러면 문제는.. 각 파일의 스코어를 구한 다음에, 스코어의 합이 0 이 되는 파일 조합중 갯수가 가장 큰것을 찾는 것이 된다.
합이 0이 되는 부분집합을 찾는 것은, 모든 부분집합을 다 뒤져야 해서 O(2^n)이 걸리는 작업이고, 그나마 Meet In the Middle테크닉을 이용하면 2^(n/2)까지 줄일수 있다. 이 문제는 딱 그 방법을 적용하라고 n≤40 으로 주어졌다, 합이 0이 되는 파일들의 부분집합중에서 블럭 갯수가 가장 많은 것을 찾도록 바꾸는 것은 별로 어려운 작업은 아니다.
결국 시간복잡도는 각 파일의 스코어를 계산하는데 O(n*m)이 걸리고, 최적의 파일들을 찾는 데에 O(2^(n/2))이 걸린다. (n은 파일의 갯수, m은 파일 안의 블럭의 갯수).
구현할때는 스코어를 저 공식대로 실수형으로 계산하면 오차가 생길수 있으니, 분모에 2^m을 곱해서 모두 정수로 만드는 것이 필요할 것이다.