증명은 잘 모르겠지만. 도움이 될 만한 질문을 드릴게요.
문제 조건 상 7개의 비트로 표현이 가능하다.
a와 b가 다르다면 7개의 비트가 모두 같을까? 아니면 최소 하나 이상의 비트가 다를까?
16438번 - 원숭이 스포츠
증명은 잘 모르겠지만. 도움이 될 만한 질문을 드릴게요.
문제 조건 상 7개의 비트로 표현이 가능하다.
a와 b가 다르다면 7개의 비트가 모두 같을까? 아니면 최소 하나 이상의 비트가 다를까?
댓글을 작성하려면 로그인해야 합니다.
gustn3065 3년 전
이것저것 고민하다가 문득 log2(99)는 6.6이라는 것을 깨닫고,
이분탐색으로 절반씩 바꿔주며 정답열에 추가해주면 모든 두 원숭이들이 최소 한번은 적으로 만날꺼라고 생각되었습니다.
하지만 제 머릿속으로는 타당한근거가 떠오르지 않는데요 ㅠ
왜 절반씩 나눠주면 최소 한번씩 적으로 만나게될까요???
절반씩나눠준다는 의미는,
처음에 길이만큼 11111111로 시작하여,
반을 기준으로 왼쪽은 값을 유지하고, 오른쪽은 값을 변경하도록 했습니다.
그러고 나뉘어진 왼쪽, 오른쪽을 똑같이 탐색하도록 했습니다
그러면 값은 총
11111111,
11110000,
11000011,
10010110 ..이런식으로 됩니다.