| [ QuizWit ] in KIDS 글 쓴 이(By): valken (> 아슈람 <롔) 날 짜 (Date): 1997년07월21일(월) 19시15분28초 KDT 제 목(Title): Re: [답] 셔플 문제 - valken 제가 만들어 본 프로그램은 다음과 같습니다.. 1) 2,4,8,16 중에 하나 고르거나 하나도 안고른다. 2) 3,9,27 중에 하나 고르거나 하나도 안고른다. 3) 5,25 중에 하나 고르거나 하나도 안고른다. 4) 7,11,13,17,19,23 각각에 대해서 고르거나 안 고른다.. 5) 이렇게 선택한 수들의 합이 52이하인지 확인한다. 6) 52 이하라면,, 그 곱이 어느 정도(저는 50000으로) 이상일 경우 각 수들을 나열하고 곱을 출력한다.. 7) 만약 수의 합이 정확하게 52가 아니라 그보다 적다면, 나머지는 1로 채운다. 8) 가능한한 모든 경우에 대해서 반복 수행한다.. 여기서는 5x4x3x(2^6) 가지 경우에 대해서 모두 확인해 본것입니다.. .. 이 문제는 지난학기 골치를 썩혔던 0/1 Knapsack 과 비슷한 면이 보이네용. bounding 도 가능할것 같고.. 일반적인 경우에 대해서 알고리즈믹하게 기술도 가능할것 같네용.. 1) 2,4,8,...2^k(<n) 중에서 하나 고른다.. 2) 3,9,27... 3^k(<n) 중에서 하나 고른다.. 3) n 보다 작은 솟수(소수)에 대해서 이 같은 과정을 수행한다. 4) 합이 n 보다 작거나 같은지 확인 한다.. 5) 곱의 최대값을 구한다.. 단 time complexity 는 책임 질수 없네용.. :( n 보다 작은 솟수의 갯수는 아는 바가 없어서리.. - 아슈람 - - Valken the SEXy THief~~ ^_* - |