I. Guess the Animal

Editor: 김정현(powergee)

문제 상황 설명

Bessie와 Elsie가 동물을 맞추는 놀이를 하고 있습니다. Bessie가 어떤 동물을 생각하고, Elsie가 그 동물의 특성에 대한 질문을 하면 Bessie가 그에 대한 답을 "예", "아니요"로 답을 합니다. 이렇게 Bessie가 생각하는 동물이 확정될 때까지 (모든 질의응답에 상응하는 동물이 단 하나 뿐일 때까지) 질문을 하는데 "예"를 가장 많이 받는다면 최대 몇 번이나 받을 수 있을까요?

문제 풀이

"예"를 최대한 많이 받으려면, Bessie가 생각하는 동물의 특성만을 물어봐야 함은 자명합니다. 그런데 여기서 그 동물의 여러가지 특성들 중 어떤 특성들을, 어떤 순서로 물어야 할지에 대한 의문이 생기게 됩니다. 이를 알아보기 위해 아래와 같은 예제와 함께 생각해보겠습니다.

입력이 아래와 같이 주어졌다고 해보겠습니다.

2
Cow 6 A B C D E F
Human 4 A B C D

위 예제에서 Cow와 Human은 4가지 공통된 특성을 공유하고, Cow만이 가진 2가지 특성이 있습니다. 이 경우에서는 Bessie가 둘 중 Cow를 생각하고, Elsie가 처음에 공통된 A, B, C, D 특성을 임의의 순서로 질의한 뒤 E, F 중 둘 중 하나를 질의한다면, 5번의 "예"를 받고 동물이 확정되기 때문에 정답은 5입니다. (만약 Bessie가 Human을 생각한다면 최대 4번의 "예"를 받을 수 있기 때문에 정답에 해당되지 않습니다.) 이때 놀이의 흐름은 아래와 같습니다.

1. A를 질의하면 "예"를 받고 아무 동물도 제외되지 않습니다.

2. B를 질의하면 "예"를 받고 아무 동물도 제외되지 않습니다.

3. C를 질의하면 "예"를 받고 아무 동물도 제외되지 않습니다.

4. D를 질의하면 "예"를 받고 아무 동물도 제외되지 않습니다.

5. E를 질의하면 "예"를 받고 Human이 제외됩니다. 이 시점에서 동물이 확정됩니다.

위를 토대로, 동물의 수가 2종류라면, 정답은 (공유되는 특성의 수) + 1과 같다는 것을 쉽게 유추할 수 있습니다.

동물의 수가 3종류 이상일 때도 위의 풀이를 응용하게 됩니다. N 종류의 동물들 중에서 Bessie가 특정 동물을 생각했을 때, 그 특정 동물의 특성을 질의하면서 그 외 N-1개의 종류가 제외되는데, 그 과정은 Bessie가 생각한 동물과 다른 하나의 동물을 포함한 2종류에 대한 질의를 할 때와 정답이 같습니다. 이를 아래 예제를 통해 부가 설명하겠습니다.

4
Cow 6 A B C D E F
Human 4 A B C D
Bird 2 A B
Goat 1 Z
Bear 3 C D E

위 예제는 첫번째 예제에서 Bird, Goat, Bear를 추가한 예제입니다. 여기서 추가한 3가지 동물은 정답에 영향을 주지 못하고 정답은 그대로 5가 됩니다. 그 이유는 Bessie가 Cow를 생각했을 때 놀이의 흐름이 아래와 같기 때문입니다.

1. A를 질의하면 "예"를 받고 Goat와 Bear가 제외됩니다.

2. B를 질의하면 "예"를 받고 아무 동물도 제외되지 않습니다.

3. C를 질의하면 "예"를 받고 Bird가 제외됩니다.

4. D를 질의하면 "예"를 받고 아무 동물도 제외되지 않습니다.

5. E를 질의하면 "예"를 받고 Human이 제외됩니다. 이 시점에서 동물이 확정됩니다.

이 예제에서 Cow와 Human은 첫번째 예제처럼 4번까지 제외되지 않고 남습니다. 여기서 유추할 수 있는 사실은, 입력으로 주어지는 동물의 수가 3가지 이상이라도 여러 번의 질의 후 끝까지 남는 한 쌍을 정할 수 있고, 그 한 쌍이 정답을 결정하게 된다는 것입니다. 그러므로 문제 해결을 위해서는 그 한 쌍이 무엇인지를 탐색해야 하고, 문제의 정답은 아래와 같이 정리할 수 있습니다.

$f(a_1, a_2)$를 "(동물 $a_1$과 $a_2$가 공유하는 특성의 수) + 1"이라고 정의할 때, 모든 조합 $(a_1, a_2)$에 대하여 $f(a_1, a_2)$의 최댓값

정답 소스 (C++)

아래 소스에서 PropIndex, NameIndex 함수는 문자열을 0이상의 인덱스로 바꾸는 함수입니다.

#include <iostream>
#include <string>
#include <unordered_map>
#include <set>
#include <vector>
#include <algorithm>

std::unordered_map<std::string, int> propMap;
int propNextIndex = 0;

int PropIndex(const std::string& name)
{
    auto found = propMap.find(name);
    if (found == propMap.end())
    {
        propMap[name] = propNextIndex;
        return propNextIndex++;
    }
    else
        return found->second;
}

std::unordered_map<std::string, int> nameMap;
int nameNextIndex = 0;

int NameIndex(const std::string& name)
{
    auto found = nameMap.find(name);
    if (found == nameMap.end())
    {
        nameMap[name] = nameNextIndex;
        return nameNextIndex++;
    }
    else
        return found->second;
}

std::vector<std::set<int>> animalToProp;

int CommonPropCount(int ani1, int ani2)
{
    std::vector<int> interSec(animalToProp[ani1].size() + animalToProp[ani2].size());
    auto endIt = std::set_intersection(animalToProp[ani1].begin(), animalToProp[ani1].end(),
        animalToProp[ani2].begin(), animalToProp[ani2].end(), interSec.begin());

    return endIt - interSec.begin();
}

int main()
{
    std::cin.sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i)
    {
        std::string name;
        std::cin >> name;
        int nIndex = NameIndex(name);
        animalToProp.push_back(std::set<int>());

        int count;
        std::cin >> count;
        for (int i = 0; i < count; ++i)
        {
            std::string property;
            std::cin >> property;
            int pIndex = PropIndex(property);

            animalToProp[nIndex].insert(pIndex);
        }
    }

    int result = -1;

    for (int ani1 = 0; ani1 < n; ++ani1)
        for (int ani2 = 0; ani2 < ani1; ++ani2)
            result = std::max(result, CommonPropCount(ani1, ani2));

    printf("%d", result + 1);

    return 0;
}