스스로 풀이를 완성하지는 못했고, 이것저것 자료들을 찾아보면서 풀게 되었는데 과정을 좀 적어보겠다. 풀이 자체는 링크된 글들에 다 있으니 패스..
https://stonejjun.tistory.com/55 에는 풀이와 더불어, 풀이에 도달하기까지의 과정이 잘 정리되어있다. 저런 고수들도 나와 비슷한 관찰, 비슷한 추측, 비슷한 시도와 비슷한 실패의 과정을 거치면서 풀이를 찾아간다는 부분이 약간 위안이 되었다. 하지만 결론에서 간략한 증명 부분에서 좀 정확히 이해가 안된 부분이 있어서 저것으로 충분한지에 대해 확신이 잘 안들었고.. 다른 자료들을 더 찾아봤다.
https://pa-ni.tistory.com/20 에서는 모든 약수로 나눠보는 대신에, 3으로만 나눠보는걸로도 충분하다고 주장한다. 그리고 그 외에는 a-b=c-d 와 a-b=c-d+1 두가지 케이스만 추가로 처리하면 된다고 한다. 모든 약수로 나누지 않고 3으로만 나눠봐도 되는게 맞는지, 그리고 약수로 나누는 방법 말고는 저 두가지 케이스만 처리하면 충분한지에는 여전히 확신이 없었다.
https://alreadysolved.tistory.com/56 에서는 룰기반으로 처리하는 대신에 그냥 탐색을 통해서 다 해보는 방법으로 풀고 있다. 기본적으로 탐색 깊이의 상한은 정해져있고, 관찰을 통해서 a_i의 하한을 알수있기 때문에 그것을 이용으로 가지치기를 하면 시간 안에 돌아간다고 한다. 그 외에도 Brauer chain으로 가정하면 더 빠르게 풀수 있었지만, 그 가정은 그냥 실험적으로만 증명했다고 했다.
이 내용이 논문의 본론인건 아니고, 서론에서 기존에 알려진 정리들을 언급해주는 부분이라서 증명은 없다. 레퍼런스로는 크누스의 TAOC 2권이 달려있다.
비트가 3개 이하로 켜져 있을때에는 bit_length + bit_count - 2 가 최소 횟수인 것이 맞다
비트가 4개 켜져 있을 때에는 다음의 네가지 경우만을 제외하고는 bit_length + bit_count - 2 가 최소 횟수이다
1. a − b = c − d
2. a − b = c − d + 1
3. a − b = 3 and c − d = 1
4. a − b = 5 and b − c = c − d = 1
이 네가지 경우에는 횟수를 한번 더 줄인 bit_length + bit_count - 3 에 가능하다.
1번과 2번 경우는 처음부터 계속 염두에 두고 있었던 것이고, 3번 경우는 3으로 나누는 경우를 일반화시키는 과정에서 알게 된 것이었다. 4번은 떠올리지 못했던 것인데, 그런데 재밌게도 4번 케이스를 정리하면 항상 3의 배수가 되고 이 경우에서 횟수 단축이 되도록 만드는 방법은 3으로 나누는 것이다.
그래서, 결국 3으로 나누는 케이스를 처리하면 3,4번이 커버되므로, 3으로 나누기 + 1,2번케이스 를 처리하면 정답을 얻을 수 있는게 맞았다.
또한, 이 네가지 케이스를 실제로 처리하는 과정을 보면 Brauer chain으로 만들어질 수 있다는 것도 확인할 수 있었다.