| [ QuizWit ] in KIDS 글 쓴 이(By): valken (:이쁜왕자:) 날 짜 (Date): 2003년 4월 14일 월요일 오전 11시 19분 14초 제 목(Title): Re: 아우토반의 오토바이 II 1,2 번 모두 옵티말 전략의 척도는 '시간'이니깐, 그냥 단순하게 시간으로 생각했습니다. 그리고 지수형태로 시간을 늘려 나간다라고 생각했습니다. 그러니깐, 1 초동안 가속(2번에서는 등속)을 한뒤, 버튼을 누른다. 실패하면, x 초동안 가속한뒤, 버튼을 누르고, 실패하면, x^2 초 동안 가속한뒤..... x^n 초 동안 가속후 속도가 S_escape 보다 크다면 탈출 성공이고, (2번 문제에서는 x^n 초 동안 직진후에 거리가, 탈출점 보다 멀면 성공) 이때까지 걸린 시간을 최소화 시키는 x 과 n 를 구한다는 전략을 생각했습니다. 걸린 시간은 ( 1 + x + x^2 + ... + x^(n-1)) * 2 + x^n 입니다. 이를 정리한뒤 적당히 근사하면, 2(x^n -1) x+1 --------- + x^n = ----- * x^n (x-1) x-1 그리고, x^n >= TS ( TS 는 S_escape 까지 가속하는데 걸리는 시간) 이죠. 역시나 x^(n-1) < TS 니깐. 양번에 x 을 곱하면, TS < x^n <= x * TS 가 됩니다. 이를 대입하면 걸리는 시간은 최대 x(x+1) ------- * TS 가 됩니다. x-1 ,,,, 다시 말해서, 적당한 x 를 선택하면, 이는 옵티말 알고리즘 (S_escape 를 알아내서, TS 만큼 가속한뒤 탈출하는 경우) 보다 x(x+1) / (x-1) 배 보다는 느리지 않는 결과를 얻을 수 있습니다. x = 2.3 정도에서 최소 값을 가질듯 하네요. "웬 초콜릿? 제가 원했던 건 뻥튀기 쬐끔과 의류예요." "얘야, 왜 또 불평?" -> 자음 19개와 모음 21개를 모두 사용하는 pangram - 이쁜왕자 - - Valken the SEXy THief~~ ^_* - |