ps:problems:boj:15134
목차
Dividing Marbles
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 15134 |
| 문제명 | Dividing Marbles |
| 레벨 | 루비 5 |
| 분류 |
애드혹 |
| 시간복잡도 | O(T*d) |
| 인풋사이즈 | T<=500, d<=20 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 32412KB / 52ms |
| 최고기록 | 52ms |
| 해결날짜 | 2026/03/31 |
풀이
- 스스로 풀이를 완성하지는 못했고, 이것저것 자료들을 찾아보면서 풀게 되었는데 과정을 좀 적어보겠다. 풀이 자체는 링크된 글들에 다 있으니 패스..
- 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 에서 알게된 Addition Chain 이라는 키워드를 사용해서 좀더 찾아보았다.
- 이 문제는 Addition Chain 이라는 나름 유명한 문제이고, 이 문제는 기본적으로 NP-complete이다. 관련된 정리나 아직 증명안된 추측도 많은 분야이다.
- 그리고, 내가 궁금했던 내용에 대해서는 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으로 만들어질 수 있다는 것도 확인할 수 있었다.
코드
- 다이아몬드 이상은 코드 생략
ps/problems/boj/15134.txt · 마지막으로 수정됨: 2026/03/31 02:07 저자 teferi
토론