[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

  Comments
  • 초보
    안녕하세요, 바킹독님 코드 분석하다가 이해가 안되서 질문 좀 드릴게요.

    Result ret = query(guess);
    int cand[5040][4]; // 정답으로 가능한 후보군을 계속 가져갈 것이다.
    int len = 0; // len은 후보군의 갯수

    for(int i = 0; i < 5040; i++){
    Result score = getScore(guess, valid_ball[i]); // 정답이 digit일 수 있는가 확인하고 싶은 것이다.

    // cout << score.S << ' ' << score.B << '\n';
    if(score.S != ret.S or score.B != ret.B) continue;
    for(int j = 0; j < 4; j++) cand[len][j] = valid_ball[i][j];
    len++;
    }

    여기서 guess 랑 valid_ball 이랑 스코어 계산해서 candi 로 왜 옮겨야 하는 건가요 ? 이미 가능한 후보는 valid_ball 에 다 저장해논 거 아닌가요?
  • 초보
    그 후에 표준편차를 구하는? while 문 안의 코드도 잘 이해가 안됩니다....ㅠ,ㅠ
    1. rrand 와 rrand2 를 왜 따로 구하는 지
    2. cnt[5][5] 배열에 strike 와 ball 을 카운트해서 mean 에 더하는 이유
    3. 아래 코드가 전체적으로 뭘 하는 건지 도저히 이해가 안됩니다...ㅠ,ㅠ
    전체적인 흐름이라도 알려주시면 감사하겠습니다.

    int cnt[5][5]={}; // cnt[i][j] : strike가 i개, ball이 j개인 갯수
    for(int j = 0; j < len; j++){
    Result score = getScore(valid_ball[rrand], cand[j]);
    cnt[score.S][score.B]++;
    }

    double mean = 0;
    double devi = 0;

    for(int i = 0; i <= 4; i++){
    for(int j = 0; j <= 4-i; j++){
    mean += cnt[i][j];
    }
    }

    for(int i = 0; i <= 4; i++){
    for(int j = 0; j <= 4-i; j++){
    devi += (cnt[i][j]-mean)*(cnt[i][j]-mean);
    }
    }

    if(devi < bestdevi){
    for(int i = 0; i < 4; i++) bestguess[i] = valid_ball[rrand][i];
    bestdevi = devi;
    }
    }

    • doUserImplementation 함수는 아래와 같은 흐름으로 진행됩니다.

      1. 4자리가 모두 다른 수들을 valid_ball에 다 담습니다.(line 31 to 47)

      2. 1297을 보내어 몇S 몇B인지 확인하고, S와 B가 일치하는 것만 cand에 담습니다.(line 49 to 58)

      예를 들어 1297을 보냈는데 2S 1B이라면 1289는 cand에 담기지만 2481은 cand에 담기지 않습니다.

      3. 이후 후보군이 1개로 확정될 때까지 '적절한' 질의를 하고, 그 응답으로 날아온 Strike Ball을 가지고 cand를 갱신하는 것을 반복합니다.

      질문을 하신 대부분의 내용들이 이 3번 과정을 코드로 작성한 부분에서 생긴 의문들인 것 같습니다.

      저는 3번 과정에서 필요한 '적절한' 질의를 '가능한 결과들의 표준편차가 작은 것'으로 정의했습니다. 예를 들어 현재 남아있는 후보군이 {1234, 2345, 1345, 1235}라고 하겠습니다.

      이 때 질의를 5789로 보낸다면 0S0B이 1개 / 0S1B가 3개입니다.

      반면 질의를 1234로 보낸다면 4S이 1개 / 3B이 1개 / 1S2B이 1개 / 3S가 1개 나옵니다.

      즉 5789보다 1234가 더 좋은 질의이고, 다른 말로 표현하면 1234는 가능한 결과들의 표준편차가 작습니다. 마치 업다운 게임에서 수가 1에서 50 사이일 때 맨 처음에 49나 2를 부르는 대신 25를 부르는 이유와 똑같이 생각할 수 있습니다.

      cnt 변수는 표준편차를 계산하기 위해 각 결과가 몇 개 등장했나 세는 변수입니다.

      rrand 부분은 그냥 rrand에 0에서 5039 사이의 난수를 넣고 싶은데, rand() 함수를 사용할 수 없으니 68번줄과 같이 rrand2가 매번 다른 난수가 나오도록 했습니다.

      표준편차가 잘 이해가지 않는다면 표준편차와 관련된 부분을 날려버리고 그냥 현재 후보군중에 가장 앞의 것을 보낸 후 그 결과에 따라 후보군을 필터링하는 정도로만 구현을 하셔도 큰 문제가 없을 것입니다.
  • 절대모보해
    아 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ첫 guess를 아무렇게 넣어도 되나 싶어서 찾아봤는데 주석에 my phone number ㅎㅅㅎ 하신거 보고 너무 귀여우셔서 댓글 달아요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ 소스코드 잘 참고하겠습니다 감사합니다!!
댓글 쓰기