[SW Expert Academy] 1768. [SW Test 샘플문제] 숫자야구게임

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4su3xKXFUDFAUf

기본적으로 현재의 질의 결과 상 가능한 후보군을 계속 줄여나가서 후보군이 1개로 확정될 때 그 답을 출력하게끔 하는 방식으로 구현을 하면 됩니다.

그런데 현재의 후보군에서 어떤 물어보는 수로 물어봐야 좋을지를 정하는게 문제인데, 일단 질의를 했을 때 가능한 그룹(4S0B, 3S0B, 3S1B, 2S0B, 2S1B, 2S2B, 1S0B ,...)끼리의 표준편차가 작은게 유리할 것입니다. 업다운 게임을 할 때 1에서 50까지의 수 중 하나일 경우 49나 2를 부르지 않고 25를 부르는 이유와 동일합니다. 5040개의 물어보는 수에 대해 표준편차를 다 구해보는 방식을 쓴 결과 시간초과가 발생해서 현재의 후보군+1000개의 랜덤한 물어보는 수 중에서 표준편차가 가장 작은 것을 선택하도록 했습니다.

랜덤한 1000개 테스트케이스에 대해 실험해보니 제 알고리즘은 4977번의 query를 사용했습니다. 즉 각 TC에서 평균적으로 4.98번의 query를 필요로 했습니다. 

https://github.com/blisstoner/SW-Expert-Academy/blob/master/1768.cpp