gustn3065   3년 전

이것저것 고민하다가 문득 log2(99)는 6.6이라는 것을 깨닫고, 

이분탐색으로 절반씩 바꿔주며 정답열에 추가해주면 모든 두 원숭이들이 최소 한번은 적으로 만날꺼라고 생각되었습니다.

하지만 제 머릿속으로는 타당한근거가 떠오르지 않는데요 ㅠ  

왜 절반씩 나눠주면 최소 한번씩 적으로 만나게될까요??? 

절반씩나눠준다는 의미는, 

처음에 길이만큼 11111111로 시작하여,

반을 기준으로 왼쪽은 값을 유지하고, 오른쪽은 값을 변경하도록 했습니다.

그러고 나뉘어진 왼쪽, 오른쪽을 똑같이 탐색하도록 했습니다

그러면 값은 총 

11111111,  

11110000, 

11000011,  

10010110 ..이런식으로 됩니다. 

chogahui05   3년 전

증명은 잘 모르겠지만. 도움이 될 만한 질문을 드릴게요.

문제 조건 상 7개의 비트로 표현이 가능하다.

a와 b가 다르다면 7개의 비트가 모두 같을까? 아니면 최소 하나 이상의 비트가 다를까?

gustn3065   3년 전

답변 달아주셔서 감사합니다 고민해보겠습니다

댓글을 작성하려면 로그인해야 합니다.