| [ QuizWit ] in KIDS 글 쓴 이(By): guest (guest) 날 짜 (Date): 1997년07월22일(화) 07시13분37초 KDT 제 목(Title): shuffling 17이 최대인 경우를 생각해 보면 역시 기본으로 2,3은 들어간다. 만일 5가 등장하지 않으면 7, 11이 있어야 한다. 2+3+7+11+13+17은 52를 넘으므로 13은 없어야 한다. 그러니까 2+3+7+11+17=40. 12가 남고 이것은 역시 2를 8로, 3을 9로 바꾸어서 최대가 된다. 8+9+7+11+17. lcm=94248. 그러면 5가 있는 경우를 생각하자. 2+3+5+17=27. 25가 모자란다. 7이 나오는 경우를 생각하자. 이제 11조차도 나온다면, 13은 나오지 않는다. 이때 모자라는 수는 7. 역시 2와 3을 끌어올려야 하는데 2를 8로 바꾸는 것이 최적: lcm=8*3*5*7*11*17=157080. 11이 나오지 않는다면, 13은 나오거나 말거나 둘 중 하나. 13이 나온다면, 모자라는 수는 5. 이것은 2를 4로 바꾸고 1을 세개 추가하는 것으로 해결: lcm=4*3*5*7*13*17=92820. 13이 나오지 않는다면 모자라는 18을 2,3,5,7의 파워를 올려서 채워야 한다. 7을 더 이상 올릴 수가 없고, 5도 못 올린다. 3은 파워를 2로 올릴 수 있고, 2는 파워를 4까지로 올릴 수 있다. 3을 2까지 올라고 2를 3까지 올리거나, 3을 그냥 두고 2를 4까지 올리는 수 밖에 없다. 전자가 최적해: lcm=8*9*5*7*17=42840. 그럼 7이 나오지 않는 경우를 생각할 차례. 11과 13이 둘 다 나온다면 1밖에 남지 않는다. lcm=2*3*5*11*13*17=72930. 11만 나온다면, 남는 숫자는 14. 13은 안 나오니까 2,3,5,11의 파워를 올려야 한다. 5와 11의 파워를 올릴 수는 없고, 3은 한 단계, 2는 세 단계까지 올릴 수 있다. 3을 한 단계, 2를 두 단계 올려서 8*9로 만들어야 한다. lcm=8*9*5*11*17=67320. 13만 나온다면, 남는 숫자는 12. 역시 2,3,5,13의 파워를 올려야 한다. 이때도 lcm=8*9*5*13*17=79560. 끝으로 11,13이 다 나오지 않는다면, 남는 숫자 25 전체를 2,3,5의 파워를 올려서 해결해야 한다. 5는 25로 쓰인다면 남는 수는 5. 이것은 2를 4로 바꾸어야 하는 경우이고 lcm=4*3*25*17=5100. 5가 그냥 5로 쓰인다면 여전히 25가 남고, 3은 이때 27까지 올라갈 수 있고 2는 16까지 올라갈 수 있는데 이래 봤자 lcm<=16*27*5*17=36720. 결국 여태까지 한 것에서의 최대는 157080이다. 이제 13이 최대인 경우와 11이 최대인 경우만 다루면 된다. 헥헥. |