| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1997년12월01일(월) 16시01분56초 ROK 제 목(Title): Re: Re: 파일문제. - valken 그런 변형을 허용한다면.. { 1,2,4,6,10 } 에서 그냥 10 무더기에서 10개 뽑으면 되겠군요. :) 최소한 한 무더기에서 1개 이상은 뽑아야 한다는 가정을 붙이면 어떻게 될까요? valken 님의 답도 이 경우엔 성립하지 않습니다. 같은 숫자가 여러개 있으면... trivial 한 solution은... {1, 2, 4, 6, 10} 을 가지고 하면... n = 5 1) 모든 무더기에서 전부 다 뽑아 한 무더기로 만든다. {23} 이걸 무더기 X라고 부르자. 2) 여기서 첫번째 무더기부터 만든다. i 번째 무더기를 만들 때, 1 ~ (i-1) 번째 무더기에서는 1개씩 뽑고, 무더기 X에서는 a(i) + (n-i) - (i-1) 개를 뽑느다. {5, 18} {4, 5, 14} {3, 4, 6, 10} {2, 3, 5, 7, 6} {1, 2, 4, 6, 10} 이게 모든 경우를 다 cover할 것 같지는 않네요. 그리고, 마지막 두 단계에서 무더기 갯수가 그대로인 걸 개선할 수도 있을 것 같고요. -- 박종대 |