| [ QuizWit ] in KIDS 글 쓴 이(By): guest (guest) 날 짜 (Date): 1997년07월22일(화) 20시20분58초 KDT 제 목(Title): Re: [궁금] shuffling 풀이... 9조각으로 나누었더니 최적해가 된 것은 우연입니다. 더 잘게 자르기는 힘듭니다. 직관적으로 생각해서, 예를 들어 52조각으로 자른다면 1밖에는 만들어지지 않기 때문에 lcm이 커지지 않습니다. 그렇게 심하게 자르지 않는다고 해도, 너무 많이 자르면 나오는 숫자가 비교적 적어지는데, 그러면 서로 겹치는 것이 많이 생기기 때문에 lcm에는 별로 기여를 하지 않습니다. 최적의 솔루션에서 모든 m_i가 솟수의 파워였던 것은(1도 포함해서 ^^), 이유가 있습니다. m_1,m_2,...,m_r이 최적해라고 가정합시다. 그리고 만일 m_1이 서로 소인 a,b의 곱으로 나뉜다고 가정합시다. 물론 trivial한 경우를 제하기 위해 a,b>1이라고 해야겠지요? 이 경우 ab>=a+b가 성립하고, m_1 대신에 a,b그리고 모자라는 숫자를 메우는 1로 교체할 수가 있습니다. 어차피 m_1을 서로 소인 a,b로 나누면 그렇게 교체해도 lcm은 그대로 보존됩니다. 이렇게 솟수의 파워가 아닌 숫자가 있을 때 마다 모두 쪼개주면 결국은 모든 m_i는 솟수의 파워가 됩니다. 이것이 솟수의 파워만을 조사해도 되는 이유입니다. |