Q2. 과반수!
집에서 잉여하게 살던 창식이는 어느 날 친구로부터 부탁을 받게 됩니다. 친구는 수들에 대해 연구하는 작업을 하고있는데,
요새 자주 하는 일은 수들 중에서 과반수를 차지하는 어떠한 수가 존재하는가? 에 대해서 연구하고 있습니다.
Ex1) (1, 2, 3, 2) 이라는 네 개의 수가 주어졌다면 과반수인 수가 없으므로 정답은 No가 됩니다.
Ex2) (1, 2, 2) 이라는 세 개의 수가 주어졌다면 2가 과반수(절반 초과)이므로 정답은 Yes가 됩니다.
하지만 여기에는 문제가 있습니다. 수들이 주어지기는 하는데, 여러분은 정확히 그 수가 뭔지 알 수가 없습니다.
그 수들이 무엇인지는 오로지 날아다니는 스파게티 괴물(FSM)님만 알기 때문에, 질문을 해서 답을 얻어내야 합니다.
여러분이 할 수 있는 질문은 오로지, FSM님에게 어떠한 수가 다른 수와 같은지 다른지만 질문 할 수 있습니다.
Ex1) 첫번째 수와 두번째 수는 다르니? --> 응
Ex2) 두번째 수와 세번째 수는 다르니? --> 아니
친구가 고민인건, 질문을 할 때마다 FSM님에게 수백kg의 라면을 바쳐야하기 때문에
최대한 질문 수를 줄이면서 과반수를 차지하는 어떠한 수가 존재하는지 알고 싶다는 것이죠.
친구를 도와봅시다.
P1) 3개의 수가 주어졌습니다. 최악의 경우 몇 번의 질문을 해야 할까요?
P2) 4개의 수가 주어졌습니다. 최악의 경우 몇 번의 질문을 해야 할까요?
P3) N개의 수가 주어졌습니다. 최악의 경우 몇 번의 질문을 해야 할까요?
글쓰기