글 읽기 - 테스트 케이스는 전부 다 성공하는데 반례가 안되는데 뭐가 있을까요

smiley_bin 4년 전 0

이미 올라온 질문의 반례도 해보았는데 성공했습니다. 어떤 반례가 또 있을까요 !?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector <pair<short, short>> A;
vector <pair<short, short>> A_tmp;
vector <short> ans;
int main(void) {
   for (int i = 0; i < 9; i++) {
      pair <short, short> in;
      cin >> in.first >> in.second;
      A.push_back(in);
   }

   for (int i = 0; i < 9; i++) {
      short check[9];
      for (short a = 0; a < 9; a++)
         check[a] = -1;

      A_tmp = A;
      if (A_tmp[i].first == 0)
         A_tmp[i].first = 1;
      else A_tmp[i].first = 0;
      bool ctd = false;

      for (int j = 0; j < 9; j++) {
         if (A_tmp[j].first == 0) {
            if (check[A_tmp[j].second - 1] == 1) {
               ctd = true;
               break;
            }
            else check[A_tmp[j].second - 1] = 0;
         }
         else if (A_tmp[j].first == 1) {
            if (check[A_tmp[j].second - 1] == 0) {
               ctd = true;
               break;
            }
            else check[A_tmp[j].second - 1] = 1;
         }
      }
      if (!ctd) {
         short ok_0 = 0;
         short ok_1 = 0;
         short ok_m1 = 0;
         short tmp_ans_1;
         short tmp_ans_2;
         for (int x = 0; x < 9; x++) {
            if (check[x] == 0)  ok_0++;
            else if (check[x] == 1) {
               ok_1++;
               tmp_ans_1 = x;
            }
            else {
               ok_m1++;
               tmp_ans_2 = x;
            }
         }
         if (ok_1 == 1) ans.push_back(tmp_ans_1 + 1);
         else if (ok_0 == 8) ans.push_back(tmp_ans_2 + 1);
      }
   }
   bool f_ans = true;
   for (int x = 1; x < ans.size(); x++) {
      if (ans[0] != ans[x]) {
         f_ans = false;
         break;
      }
   }
   if (f_ans && ans.size()>0)
      cout << ans[0];
   else cout << -1;

   return 0;
}

sait2000 4년 전 11

코드가 틀릴 수 있는 방법은 매우 다양하기 때문에 틀린 코드라도 올라온 질문에 있는 모든 반례가 통과할 수 있습니다. (사실, 꽤 흔한 모양입니다. 다들 그렇게 말씀하시는 거 보면) 그러면 자기 코드는 남들과는 다른 또다른 방법으로 틀렸다고 생각하시면 됩니다.

각설하고 테스트케이스에 대한 설명을 좀 하겠습니다. 문제를 잘못 해석하면 첫번째 줄이 거짓이고 1번이 1루수인 가능성만 있는 것 같지만, 진짜 가능한 모든 경우는 다음과 같습니다.

1째 줄이 거짓이고 1번이 1루수
2째 줄이 거짓이고 8번이 1루수
2째 줄이 거짓이고 9번이 1루수

세 경우 모두 거짓말 하는 사람도 1명이고 1루수도 한 명이고 9개의 진술과도 어긋남이 없는 상황임을 알 수 있습니다. 따라서 1루수일지도 모르는 사람이 1번 8번 9번 총 3명이므로 이 경우의 출력은 -1이 돼야 합니다.

in:
1
1
2
3
4
5
6
7
7

out:
-1

smiley_bin 4년 전 0

질문마다 좋은 답변과 반례 주셔서 감사합니다!

cequala 3년 전 0

여기 sait님 답변은 FAQ로 등록해도 될 것 같습니다ㅎㅎ 저도 좋은 답변 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.