1~8까지 상대방이 숫자 정하고 내가 Yes or No로만 질문해서 맞추는 건데 중간에 상대방이 한 번 거짓말을 할 수도 있음(안 할 수도 있음)
제 방법은 반 씩 숫자 줄여나가는 건데(5이상? 7이상? 이런 식으로) 했던 질문을 반복해서 또 해서 거짓말은 했는지 검증하는 거에요 이런 식으로 하면 최대 7회 나옴
이거 최소횟수 7 아닌가요? 왠지 아닐 거 같아서;
제 방법은 반 씩 숫자 줄여나가는 건데(5이상? 7이상? 이런 식으로) 했던 질문을 반복해서 또 해서 거짓말은 했는지 검증하는 거에요 이런 식으로 하면 최대 7회 나옴
이거 최소횟수 7 아닌가요? 왠지 아닐 거 같아서;
bisection method 를 이용하면 됩니다. 정답이 있는 interval의 길이를 질문/답변 한번에 절반씩 줄일 수 있어요. ex) initial state: [0, 10] step 1 : ask 5, ans UP sencond state: [6, 10] ... go on - dc App
문제를 안읽으신듯
아 거짓말.. 문제를 잘못 읽었당
재밌는 문제당
글쓴 사람인데 최소횟수 6회임
어캐푸심 ㄷㄷ 컴퓨터 없으면 전 못풀듯.. 답이 1인경우 가능한 질문/응답 decision tree, 답이 2인 경우.. 해서 총 8개 tree 만들고 각각의 tree의 node에 대한 recursive function 정의하고 이를 이용해 푸는아이디어는 있는데, 당장 저 tree도 어떻게 만들지 모르겠당 ㅠ - dc App
그런데 궁금한게 질문에 대한 응답이 무조건 UP, YES, DOWN 셋 중 하나인가요? 만약 1 물어봤을 때 거짓말로 DOWN을 응답할 수 있나요? - dc App