USACO 2019 January Contest, Bronze Problem 3. Guess the Animal

USACO 2019 January Contest, Bronze 3번 문제 Guess the Animal입니다.

본 포스트는 이해를 돕기 위해 문제를 간략하게만 정리하였으므로 상세 내용과 코드 제출은 아래 링크를 참고해 주세요.

USACO

 

문제 개요 설명

---

Elsie와 Bessie가 동물 스무고개 맞추기를 하고 있습니다. 정답이 될 수 있는 동물들의 리스트가 주어지고, 각 동물들은 여러 가지의 특징을 가지고 있습니다.

 

그리고 이제 Bessie가 해당 리스트에서 선택한 동물이 무엇인지 맞추기 위해 Elsie는 이 특징들을 가지고 Bessie에게 질문을 해야 합니다. 이때 대답은 Yes 혹은 No로 이루어집니다. Elsie는 정답이 될 수 있는 가능성을 가진 동물이 하나만 남을 때까지 질문하고, 하나만 남는 경우에 정답을 맞춥니다. 

 

이 게임이 진행된다고 할 때, 정답을 맞추기 위해 Yes 대답을 받는 경우를 생각해 보겠습니다. Yes가 3번만에 정답을 맞출수도 있고 Yes가 4번만에 정답을 맞출수도 있을 것입니다.

 

이런 식으로, 주어진 리스트에서 정답을 맞추기 위해 질문 시에 받을 수 있는 Yes 대답의 최대 횟수를 구해주세요.

입력

---

• 첫번째 줄에는 몇 마리의 동물들이 후보 리스트로 주어지는지를 의미하는 정수(N)가 포함됩니다.
• 한 줄에는 동물의 이름, 특징 개수, 특징들이 포함됩니다. (총 N 줄)

출력

---

• 정답을 맞추기 위해 받을 수 있는 최대 Yes 대답의 수를 출력합니다.

 

입출력 예시

---

입력 :

4
bird 2 flies eatsworms
cow 4 eatsgrass isawesome makesmilk goesmoo
sheep 1 eatsgrass
goat 2 makesmilk eatsgrass

출력 :

3

4개의 동물 리스트가 있고, 각각 특징을 가지고 있습니다. 해당 입력의 경우 최대로 받을 수 있는 Yes 개수는 3입니다.

 

Elsie: "Does the animal fly?" 
Bessie: "No" 
Elsie: "Does the animal eat grass?" 
Bessie: "Yes" 
Elsie: "Does the animal make milk?"
Bessie: "Yes" 
Elsie: "Does the animal go moo?"
Bessie: "Yes" 
Elsie: "In that case I think the animal is a cow." 
Bessie: "Correct!"

 

솔루션 코드

---

input_file = open('guess.in','r')
output_file = open('guess.out','w')

characteristic = []
result = 0

# 특징 저장
for line in input_file:
    line = line.split()
    characteristic.append(line[2: len(line)])

# 순회하며 2마리씩 비교하기
for i in range(len(characteristic)):
    for j in range(i+1,len(characteristic)):
        common = set(characteristic[i]).intersection(set(characteristic[j]))
        result = max(len(common)+1,result)

output_file.write(str(result))

 

먼저 특징들을 저장할 리스트를 만들고 첫 번째 반복문을 이용하여 주어진 특징들을 순서대로 저장합니다.

다음으로 2마리씩 순서대로 모든 경우를 순회하며 특징을 비교합니다. (두 마리를 가지고 질문을 던집니다)

 

이때 두 동물에 대해 질문할 때 가장 많이 Yes라는 대답을 들으려면 둘의 공통된 모든 특성을 전부 다 물어보고 나서, 이제 더이상 공통되는 특성이 남아있지 않을 때 마지막 질문을 통해 정답을 구분할 수 있도록 하면 될 것입니다.

 

즉 M개의 공통 특성이 있다면 M번만큼 질문하고 거기에 답을 결정하는 질문을 한 번 더 하면 되기 때문에 총 Yes 개수는 M+1이라고 할 수 있습니다. 저는 교집합을 이용해서 공통 특성을 걸러내었습니다. 이렇게 모든 경우를 체크하여 가장 큰 수를 정답으로 저장하면 되겠습니다.

 

이렇게 두 동물의 공통 특징을 구하는 방법에서 전체 반복 순회를 하지 않고 더 효율적으로 딕셔너리나 이진탐색을 이용하여 문제를 푸는 방법도 있다고 하니 다른 방법도 함께 생각해 보면 좋을 것 같습니다.