====== Dividing Marbles ======

===== 풀이 =====
  * 스스로 풀이를 완성하지는 못했고, 이것저것 자료들을 찾아보면서 풀게 되었는데 과정을 좀 적어보겠다. 풀이 자체는 링크된 글들에 다 있으니 패스..
    * [[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으로 가정하면 더 빠르게 풀수 있었지만, 그 가정은 그냥 실험적으로만 증명했다고 했다.
    * [[https://neerc.ifmo.ru/archive/2017/northern/north-2017-analysis.pdf]] 공식 에디토리얼이다. 러시아어인데, 암튼 정해로 제시한것은 a_i의 하한을 이용해서 가지치기 하면서 전부 탐색해보는 것이다. Brauer chain은 언급하지 않는다.
  * 정리해보면 출제자의 정해는 그냥 탐색이었는데, 케이스 나눠서 룰 기반으로 처리하는 (훨씬 빠른) 방법이 통과되기는 하는 것 같았다. [[https://alreadysolved.tistory.com/56]] 에서 알게된 [[wp>Addition Chain]] 이라는 키워드를 사용해서 좀더 찾아보았다.
  * 이 문제는 Addition Chain 이라는 나름 유명한 문제이고, 이 문제는 기본적으로 NP-complete이다. 관련된 정리나 아직 증명안된 추측도 많은 분야이다.
  * 그리고, 내가 궁금했던 내용에 대해서는 [[https://eprint.iacr.org/2022/1160.pdf|The Scholz conjecture on addition chain is true for v(n)=4
]] 논문에서 쉽게 답을 찾을수 있었다. 
    * 이 내용이 논문의 본론인건 아니고, 서론에서 기존에 알려진 정리들을 언급해주는 부분이라서 증명은 없다. 레퍼런스로는 크누스의 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으로 만들어질 수 있다는 것도 확인할 수 있었다. 

===== 코드 =====
  * 다이아몬드 이상은 코드 생략

{{tag>BOJ ps:problems:boj:루비_5}}