9611. 명진이와 동휘의 숫자 맞추기 D4

명진이와 동휘가 숫자 맞추기 게임을 한다.

게임 방법은 명진이가 0 에서 9 사이의 숫자를 하나 생각하면, 동휘가 질문을 통해 명진이가 생각한 숫자가 어떤 것인지 맞추는 것이다.

동휘는 명진이가 생각한 숫자를 맞추는 데 총 N번의 질문 했다.

동휘는 질문을 한 번 할 때, 네 개의 숫자 중에 명진이가 생각한 숫자가 있는지 물어볼 수 있다.

명진이는 이 네 숫자 중에서 자신이 생각하는 숫자가 있으면 YES를, 아니면 NO를 답해 준다.

명진이가 생각한 숫자가 어떤 숫자인지 구하는 프로그램을 작성하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다.

이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다.

각 테스트 케이스는 다음과 같이 구성되어 있다.

> 각 테스트 케이스의 첫 번째 줄에 동휘가 숫자를 맞추는 데까지 질문한 횟수 N 이 주어진다. (1 ≤ N ≤ 6)

> 이후 N개의 줄의 각 줄에는 네 개의 정수 a, b, c, d 와 하나의 문자열 S가 공백 하나로 구분되어 주어진다.
   (0 ≤ a, b, c, d ≤ 9), 문자열 S 는 “YES”혹은 “NO”중 하나이다.

> 명진이가 생각한 숫자는 언제나 유일하게 결정됨이 보장되는 경우만 입력으로 주어진다.

[출력]

각 테스트 케이스마다 tc 출력하고,

명진이가 생각한 숫자가 어떤 것인지 출력한다.

 

 

음 처음에 접근을 잘못해서 시간이 오래걸렸다.

맞은 것들중에서도 안겹치면 빼야하는데 이걸 생각 못했다. 

 

일단 코드부터 적겠다.

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
int check[10],temp[10];
 
int main()
{
    int tc,ans,n;
    cin>>tc;
    for(int t=1;t<=tc;t++)
    {
        string str;
        memset(check, 0, sizeof(check));
 
        ans = 9999;
        cin>>n;
        cin.ignore();
        int cnt = 0;
        for(int i=0;i<n;i++)
        {
            getline(cin,str);
            if(str[8]=='N')
                for(int i=0;i<4;i++)
                    check[str[i*2]-'0'] = 1;
            else
            {
                if(cnt == 0)
                {
                    for(int i=0;i<4;i++)
                        if(check[str[i*2]-'0']!=1)
                            check[str[i*2]-'0'] = 2;
                    cnt++;
                }
                else
                {
                    memset(temp, 0,sizeof(temp));
                    
                    for(int i=0;i<4;i++)
                        temp[str[i*2]-'0'] = 2;
                    for(int i=0;i<10;i++)
                    {
                        if(temp[i] == check[i]&&check[i] == 2) check[i] = 2;
                        else check[i] = 1;
                    }
                }
            }
        }
        for(int i=0;i<10;i++)
            if(check[i]==2) ans = i;
 
        if(ans == 9999)
            for(int i=0;i<10;i++)
                if(check[i] == 0) ans = i;
        printf("#%d %d\n", t, ans);
    }
    return 0;
}
 

 

0은 unknown, 1은 false, 2는 true

 

요약

1. NO가 들어오면 그 숫자들은 무조건 NO

2. 처음 YES가 들어왔을 때 원래 unknown 이어서 unknown일 경우 그 숫자 true로 설정

3. 두 번째 YES부터는 처음 YES와 비교해야함

그래서 temp 배열 사용 temp는 새로 들어온 yes, 만약 후보들이 새로 들어온 input들과 동시에 true가 아니라면 그 후보는 false

4. 만약 위 조건식에 들어갔다면 남은 후보는 1개이므로 출력하면 된다.

5. 만약 모두 NO만 들어갔다면 1개만 남는데 그 후보는 unknown일 것이다. 그 경우를 찾기 위해 ans는 처음에 9999로 초기화 했다. ans는 4번의 조건에서 바뀌지 않았을 것이다. 그래서 10개중 unknown인 것은 1개만 남으므로 그걸 출력하면 된다.