| [ QuizWit ] in KIDS 글 쓴 이(By): valken (:이쁜왕자:) 날 짜 (Date): 2011년 11월 23일 (수) 오후 03시 14분 47초 제 목(Title): Re: 10개의 동전 1. 주어진 수(삼각수에 한함)에 대해서, partition generator를 구현하여 모든 파티션을 구한다. 2. 각 파티션에 대해서 '시행'을 하고, 그 결과로부터 unidirectional graph를 만든다. 3. 이 그래프에 cycle 이 존재하지 않음을 확인한다. (주: 실제로 삼각수의 경우는 cycle 이 존재하지 않는다고 합니다.) 4. 위 graph 에 대해서 역방향의 그래프 또한 만든다. 5. 역방향 그래프에서, 명백한 엔딩 조건인 n,n-1,...,2,1 로부터 시작되는 breadth first search 를 돌린다. 6. BFS 로 구한 longest path 를 찾아서 출력한다. 1번이 어려울꺼라 생각했는데, 잠시 생각해 보니 재귀호출로 간단히 해결되네요. 오히려 문제는 그 결과값이 너무 크다는거네요. p(10) = 42, p(20) = 627, p(30) = 5604, p(40) = 37338, p(50) = 204226 이고 p(100) 은 대략 1억 9000만 인데, 눈대중으로 봐도 익스포넨셜하게 증가하네요. 즉, n=100 만 되어도, 2번에서 1억 9000만개의 노드를 가지는 그래프를 만들어야 하는 상황이네요. "웬 초콜릿? 제가 원했던 건 뻥튀기 쬐끔과 의류예요." "얘야, 왜 또 불평?" -> 자음 19개와 모음 21개를 모두 사용하는 pangram - 이쁜왕자 - - Valken the SEXy THief~~ ^_* - |