| [ QuizWit ] in KIDS 글 쓴 이(By): parresia (누구게) 날 짜 (Date): 2003년 7월 18일 금요일 오전 09시 26분 19초 제 목(Title): Re: submine sux! 1차원 sub문제의 경우엔, 초기 위치 X0와 초기 속도 V0를 구하면 되는 문제이고, 이 둘이 정수라면, 언젠가는 찾을 수 있다는 점에서 finite한 시간 안에 잠수함을 찾을 수 있습니다. X0, V0를 가지는 잠수함의 T초후 위치를 T초째에 헬기가 검색하면 되므로, 이 문제는 IxI를 I에 빠짐없이 매핑할 수 있는가와 같은 문제이고, 이러한 방법중 유명한것 하나를 가지고 표를 만들자면, V0 \ X0 0 1 -1 2 -2 3 0 1 2 4 7 11 16 1 3 5 8 12 17 -1 6 9 13 18 2 10 14 19 -2 15 20 3 21 뭐 이런 식으로 정리할 수 있습니다. X0 = 0, V0=0인 잠수함의 1초째 위치(=0이겠죠)를 1초째에 검색, ... X0 = 1, V0=-1인 잠수함의 9초째 위치(=-8이겠죠)를 9초째에 검색, ... X0= -2, V0=1인 잠수함의 17초째 위치(=-2겠죠)를 17초째에 검색, ... 이런식으로 검색하는 것이죠. 이렇게 검색해 나가면 언젠가는 잠수함의 위치를 찾을 수 있습니다. 따라서 finite하죠. 물론 그 언젠가가 언제가 될지는 아무도 말할 수 없지만요. |