| [ QuizWit ] in KIDS 글 쓴 이(By): climber () 날 짜 (Date): 1998년 4월 15일 수요일 오후 03시 21분 02초 제 목(Title): [질문] 다음 조건을 만족하는 최소정수 찾� 퀴즈에 가깝다기보다는 numerical analsys에 가깝다고 해야할 문제인 듯 합니다만, 혹시 아시는 분이 있나해서 질문드립니다. 다음 조건을 만족하는 최소 정수를 찾는 알고리즘이 존재하는지? 1 + [x/a1] + [x/a2] + [x/a3] + ... + [x/an] <= x ai는 양의 정수이고, 역시 x도 양의 정수입니다. [y]는 y보다 크거나 같은 최소정수입니다. 따라서 x >= n + 1 이어야 할텐데, x가 어떤 정수 M보다 작거나 같아야한다는 제한조건하에서 위식을 만족하는 최소정수를 찾거나, 존재하지 않음을 알아내는 어떤 알고리즘이 존재하는지 알고 싶습니다. 물론 x값이 bound되어 있으므로 n+1에서부터 순서적으로 조사해보면 되겠지만, 그경우 O(M)이 걸리는데 이 보다 나은 알고리즘이 있는지 대답해 주셨으면 합니다. 미리 감사드립니다. |